Re: the elimination of if blocks in GCC during if-conversion and vectorization
Hi Richard:
Thanks for your advice. But when I try a simpler example like the one
below before looking at the code, GCC still does nothing.
int main() {
int width;
scanf("%d", &width);
int sum = 0;
for (int i = 0; i < width; i++) sum += i;
printf("%d\n", sum);
}
I tried O3 and LTO, but still the same. So I'd like to ask why, or am
I doing something wrong?
Thanks
Hanke Zhang
Richard Biener 于2023年10月19日周四 20:00写道：
>
> On Tue, Oct 17, 2023 at 2:39 PM Hanke Zhang wrote:
> >
> > Hi Richard
> > I get it, thank you again.
> >
> > And I got another problem, so I'd like ask it by the way. Can the left
> > shift of the induction variable in a loop be optimized as a constant?
> > Like the code below:
> >
> > int ans = 0;
> > int width = rand() % 16;
> > for (int j = 0; j < width; j++)
> > ans += 1 << (j + width)
> >
> > into:
> >
> > int width = rand() % 16;
> > ans = (1 << (2 * width) - (1 << width));
> >
> > I came across a more complex version of that and found that gcc
> > doesn't seem to handle it, so wanted to write a pass myself to
> > optimize it.
> >
> > I got two questions here. Does GCC have such optimizations? If I want
> > to do my own optimization, where should I put it? Put it behind the
> > pass_iv_optimize?
>
> GCC has the final value replacement pass (pass_scev_cprop) doing these
> kind of transforms. Since 'ans' does not have an affine evolution this
> case would need to be pattern matched (there are some existing pattern
> matchings in the pass).
>
> > Thanks
> > Hanke Zhang
> >
> > Richard Biener 于2023年10月17日周二 20:00写道：
> > >
> > > On Tue, Oct 17, 2023 at 1:54 PM Hanke Zhang wrote:
> > > >
> > > > Richard Biener 于2023年10月17日周二 17:26写道：
> > > > >
> > > > > On Thu, Oct 12, 2023 at 2:18 PM Hanke Zhang via Gcc
> > > > > wrote:
> > > > > >
> > > > > > Hi, I'm recently working on vectorization of GCC. I'm stuck in a
> > > > > > small
> > > > > > problem and would like to ask for advice.
> > > > > >
> > > > > > For example, for the following code:
> > > > > >
> > > > > > int main() {
> > > > > > int size = 1000;
> > > > > > int *foo = malloc(sizeof(int) * size);
> > > > > > int c1 = rand(), t1 = rand();
> > > > > >
> > > > > > for (int i = 0; i < size; i++) {
> > > > > > if (foo[i] & c1) {
> > > > > > foo[i] = t1;
> > > > > > }
> > > > > > }
> > > > > >
> > > > > > // prevents the loop above from being optimized
> > > > > > for (int i = 0; i < size; i++) {
> > > > > > printf("%d", foo[i]);
> > > > > > }
> > > > > > }
> > > > > >
> > > > > > First of all, the if statement block in the loop will be converted
> > > > > > to
> > > > > > a MASK_STORE through if-conversion optimization. But after
> > > > > > tree-vector, it will still become a branched form. The part of the
> > > > > > final disassembly structure probably looks like below(Using IDA to
> > > > > > do
> > > > > > this), and you can see that there is still such a branch 'if ( !_ZF
> > > > > > )'
> > > > > > in it, which will lead to low efficiency.
> > > > > >
> > > > > > do
> > > > > > {
> > > > > > while ( 1 )
> > > > > > {
> > > > > > __asm
> > > > > > {
> > > > > > vpand ymm0, ymm2, ymmword ptr [rax]
> > > > > > vpcmpeqd ymm0, ymm0, ymm1
> > > > > > vpcmpeqd ymm0, ymm0, ymm1
> > > > > > vptest ymm0, ymm0
> > > > > > }
> > > > > > if ( !_ZF )
> > > > > > break;
> > > > > > _RAX += 8;
> > > > > > if ( _RAX == v9 )
> > > > > > goto LABEL_5;
> > > > > > }
> > > > > > __asm { vpmaskmovd ymmword ptr [rax], ymm0, ymm3 }
> > > > > > _RAX += 8;
> > > > > > }
> > > > > > while ( _RAX != v9 );
> > > > > >
> > > > > > Why can't we just replace the vptest and if statement with some
> > > > > > other
> > > > > > instructions like vpblendvb so that it can be faster? Or is there a
> > > > > > good way to do that?
> > > > >
> > > > > The branch is added by optimize_mask_stores after vectorization
> > > > > because
> > > > > fully masked (disabled) masked stores can incur a quite heavy penalty
> > > > > on
> > > > > some architectures when fault assists (read-only pages, but also COW
> > > > > pages)
> > > > > are ran into. All the microcode handling needs to possibly be
> > > > > carried out
> > > > > multiple times, for each such access to the same page. That can cause
> > > > > a 1000x slowdown when you hit this case. Thus every masked store
> > > > > is replaced by
> > > > >
> > > > > if (mask != 0)
> > > > >masked_store ();
> > > > >
> > > > > and this is an optimization (which itself has a small cost).
> > > > >
> > > > > Richard.
> > > >
> > > > Yeah, I know that and I have seen the code of optimize_mask_store().
> > > > And the main problem here is that when multiple MASK_STORE appear in
> > > > the same loop, many branches will appear, resulting in a decrease in
> > > > overall efficiency.
> > > >
> > > > And my original idea is that why can't we replace
Re: the elimination of if blocks in GCC during if-conversion and vectorization
On Mon, Oct 23, 2023 at 12:50 PM Hanke Zhang wrote:
>
> Hi Richard:
>
> Thanks for your advice. But when I try a simpler example like the one
> below before looking at the code, GCC still does nothing.
>
> int main() {
> int width;
> scanf("%d", &width);
> int sum = 0;
> for (int i = 0; i < width; i++) sum += i;
> printf("%d\n", sum);
> }
>
> I tried O3 and LTO, but still the same. So I'd like to ask why, or am
> I doing something wrong?
-fdump-tree-sccp-details-scev reveals
(set_scalar_evolution
instantiated_below = 5
(scalar = sum_9)
(scalar_evolution = {0, +, {1, +, 1}_1}_1))
)
(chrec_apply
(varying_loop = 1)
(chrec = {0, +, {1, +, 1}_1}_1)
(x = (unsigned int) width.0_12 + 4294967295)
(res = scev_not_known))
so we don't know how to apply a variable number of iterations to
the affine expression {0, +, {1, +, 1}_1}_1, that is, we do not
know how to compute the final value of the reduction.
For a constant, say width == 100 we do:
(set_scalar_evolution
instantiated_below = 2
(scalar = sum_6)
(scalar_evolution = {0, +, {1, +, 1}_1}_1))
)
(chrec_apply
(varying_loop = 1)
(chrec = {0, +, {1, +, 1}_1}_1)
(x = 99)
(res = 4950))
Richard.
>
> Thanks
> Hanke Zhang
>
> Richard Biener 于2023年10月19日周四 20:00写道：
> >
> > On Tue, Oct 17, 2023 at 2:39 PM Hanke Zhang wrote:
> > >
> > > Hi Richard
> > > I get it, thank you again.
> > >
> > > And I got another problem, so I'd like ask it by the way. Can the left
> > > shift of the induction variable in a loop be optimized as a constant?
> > > Like the code below:
> > >
> > > int ans = 0;
> > > int width = rand() % 16;
> > > for (int j = 0; j < width; j++)
> > > ans += 1 << (j + width)
> > >
> > > into:
> > >
> > > int width = rand() % 16;
> > > ans = (1 << (2 * width) - (1 << width));
> > >
> > > I came across a more complex version of that and found that gcc
> > > doesn't seem to handle it, so wanted to write a pass myself to
> > > optimize it.
> > >
> > > I got two questions here. Does GCC have such optimizations? If I want
> > > to do my own optimization, where should I put it? Put it behind the
> > > pass_iv_optimize?
> >
> > GCC has the final value replacement pass (pass_scev_cprop) doing these
> > kind of transforms. Since 'ans' does not have an affine evolution this
> > case would need to be pattern matched (there are some existing pattern
> > matchings in the pass).
> >
> > > Thanks
> > > Hanke Zhang
> > >
> > > Richard Biener 于2023年10月17日周二 20:00写道：
> > > >
> > > > On Tue, Oct 17, 2023 at 1:54 PM Hanke Zhang
> > > > wrote:
> > > > >
> > > > > Richard Biener 于2023年10月17日周二 17:26写道：
> > > > > >
> > > > > > On Thu, Oct 12, 2023 at 2:18 PM Hanke Zhang via Gcc
> > > > > > wrote:
> > > > > > >
> > > > > > > Hi, I'm recently working on vectorization of GCC. I'm stuck in a
> > > > > > > small
> > > > > > > problem and would like to ask for advice.
> > > > > > >
> > > > > > > For example, for the following code:
> > > > > > >
> > > > > > > int main() {
> > > > > > > int size = 1000;
> > > > > > > int *foo = malloc(sizeof(int) * size);
> > > > > > > int c1 = rand(), t1 = rand();
> > > > > > >
> > > > > > > for (int i = 0; i < size; i++) {
> > > > > > > if (foo[i] & c1) {
> > > > > > > foo[i] = t1;
> > > > > > > }
> > > > > > > }
> > > > > > >
> > > > > > > // prevents the loop above from being optimized
> > > > > > > for (int i = 0; i < size; i++) {
> > > > > > > printf("%d", foo[i]);
> > > > > > > }
> > > > > > > }
> > > > > > >
> > > > > > > First of all, the if statement block in the loop will be
> > > > > > > converted to
> > > > > > > a MASK_STORE through if-conversion optimization. But after
> > > > > > > tree-vector, it will still become a branched form. The part of the
> > > > > > > final disassembly structure probably looks like below(Using IDA
> > > > > > > to do
> > > > > > > this), and you can see that there is still such a branch 'if (
> > > > > > > !_ZF )'
> > > > > > > in it, which will lead to low efficiency.
> > > > > > >
> > > > > > > do
> > > > > > > {
> > > > > > > while ( 1 )
> > > > > > > {
> > > > > > > __asm
> > > > > > > {
> > > > > > > vpand ymm0, ymm2, ymmword ptr [rax]
> > > > > > > vpcmpeqd ymm0, ymm0, ymm1
> > > > > > > vpcmpeqd ymm0, ymm0, ymm1
> > > > > > > vptest ymm0, ymm0
> > > > > > > }
> > > > > > > if ( !_ZF )
> > > > > > > break;
> > > > > > > _RAX += 8;
> > > > > > > if ( _RAX == v9 )
> > > > > > > goto LABEL_5;
> > > > > > > }
> > > > > > > __asm { vpmaskmovd ymmword ptr [rax], ymm0, ymm3 }
> > > > > > > _RAX += 8;
> > > > > > > }
> > > > > > > while ( _RAX != v9 );
> > > > > > >
> > > > > > > Why can't we just replace the vptest and if statement with some
> > > > > > > other
> > > > > > > instructions like vpblendvb so that it can be faster? Or is there
> > > > > > > a
> > > > > > > good way to do that?
> > > > > >
> > >
Re: the elimination of if blocks in GCC during if-conversion and vectorization
Richard Biener 于2023年10月23日周一 20:32写道：
>
> On Mon, Oct 23, 2023 at 12:50 PM Hanke Zhang wrote:
> >
> > Hi Richard:
> >
> > Thanks for your advice. But when I try a simpler example like the one
> > below before looking at the code, GCC still does nothing.
> >
> > int main() {
> > int width;
> > scanf("%d", &width);
> > int sum = 0;
> > for (int i = 0; i < width; i++) sum += i;
> > printf("%d\n", sum);
> > }
> >
> > I tried O3 and LTO, but still the same. So I'd like to ask why, or am
> > I doing something wrong?
>
> -fdump-tree-sccp-details-scev reveals
>
> (set_scalar_evolution
> instantiated_below = 5
> (scalar = sum_9)
> (scalar_evolution = {0, +, {1, +, 1}_1}_1))
> )
> (chrec_apply
> (varying_loop = 1)
> (chrec = {0, +, {1, +, 1}_1}_1)
> (x = (unsigned int) width.0_12 + 4294967295)
> (res = scev_not_known))
>
> so we don't know how to apply a variable number of iterations to
> the affine expression {0, +, {1, +, 1}_1}_1, that is, we do not
> know how to compute the final value of the reduction.
>
> For a constant, say width == 100 we do:
>
> (set_scalar_evolution
> instantiated_below = 2
> (scalar = sum_6)
> (scalar_evolution = {0, +, {1, +, 1}_1}_1))
> )
> (chrec_apply
> (varying_loop = 1)
> (chrec = {0, +, {1, +, 1}_1}_1)
> (x = 99)
> (res = 4950))
Yeah, I also found this result in previous experiments. But what
confuses me is that if the 'width' can't be inferred to INTEGER_CST,
there's nothing we can do, right?
Because in my case, the variables corresponding to 'width' are almost
all undetermined values, such as 'width = rand()'. That said, I can
hardly get any optimizations in my cases, right?
Thanks
Hanke Zhang
>
> Richard.
>
> >
> > Thanks
> > Hanke Zhang
> >
> > Richard Biener 于2023年10月19日周四 20:00写道：
> > >
> > > On Tue, Oct 17, 2023 at 2:39 PM Hanke Zhang wrote:
> > > >
> > > > Hi Richard
> > > > I get it, thank you again.
> > > >
> > > > And I got another problem, so I'd like ask it by the way. Can the left
> > > > shift of the induction variable in a loop be optimized as a constant?
> > > > Like the code below:
> > > >
> > > > int ans = 0;
> > > > int width = rand() % 16;
> > > > for (int j = 0; j < width; j++)
> > > > ans += 1 << (j + width)
> > > >
> > > > into:
> > > >
> > > > int width = rand() % 16;
> > > > ans = (1 << (2 * width) - (1 << width));
> > > >
> > > > I came across a more complex version of that and found that gcc
> > > > doesn't seem to handle it, so wanted to write a pass myself to
> > > > optimize it.
> > > >
> > > > I got two questions here. Does GCC have such optimizations? If I want
> > > > to do my own optimization, where should I put it? Put it behind the
> > > > pass_iv_optimize?
> > >
> > > GCC has the final value replacement pass (pass_scev_cprop) doing these
> > > kind of transforms. Since 'ans' does not have an affine evolution this
> > > case would need to be pattern matched (there are some existing pattern
> > > matchings in the pass).
> > >
> > > > Thanks
> > > > Hanke Zhang
> > > >
> > > > Richard Biener 于2023年10月17日周二 20:00写道：
> > > > >
> > > > > On Tue, Oct 17, 2023 at 1:54 PM Hanke Zhang
> > > > > wrote:
> > > > > >
> > > > > > Richard Biener 于2023年10月17日周二 17:26写道：
> > > > > > >
> > > > > > > On Thu, Oct 12, 2023 at 2:18 PM Hanke Zhang via Gcc
> > > > > > > wrote:
> > > > > > > >
> > > > > > > > Hi, I'm recently working on vectorization of GCC. I'm stuck in
> > > > > > > > a small
> > > > > > > > problem and would like to ask for advice.
> > > > > > > >
> > > > > > > > For example, for the following code:
> > > > > > > >
> > > > > > > > int main() {
> > > > > > > > int size = 1000;
> > > > > > > > int *foo = malloc(sizeof(int) * size);
> > > > > > > > int c1 = rand(), t1 = rand();
> > > > > > > >
> > > > > > > > for (int i = 0; i < size; i++) {
> > > > > > > > if (foo[i] & c1) {
> > > > > > > > foo[i] = t1;
> > > > > > > > }
> > > > > > > > }
> > > > > > > >
> > > > > > > > // prevents the loop above from being optimized
> > > > > > > > for (int i = 0; i < size; i++) {
> > > > > > > > printf("%d", foo[i]);
> > > > > > > > }
> > > > > > > > }
> > > > > > > >
> > > > > > > > First of all, the if statement block in the loop will be
> > > > > > > > converted to
> > > > > > > > a MASK_STORE through if-conversion optimization. But after
> > > > > > > > tree-vector, it will still become a branched form. The part of
> > > > > > > > the
> > > > > > > > final disassembly structure probably looks like below(Using IDA
> > > > > > > > to do
> > > > > > > > this), and you can see that there is still such a branch 'if (
> > > > > > > > !_ZF )'
> > > > > > > > in it, which will lead to low efficiency.
> > > > > > > >
> > > > > > > > do
> > > > > > > > {
> > > > > > > > while ( 1 )
> > > > > > > > {
> > > > > > > > __asm
> > > > > > > > {
> > > > > > > > vpand ymm0, ymm2, ymmword ptr [rax]
> > > > > > > > vpcmpeqd ymm0, ymm0, ymm1
Riscv code generation
Hi
In a previous post I pointed to a strange code generation`by gcc in the
riscv-64 targets.
To resume:
Suppose a 64 bit operation: c = a OP b;
Gcc does the following:
Instead of loading 64 bits from memory gcc loads 8 bytes into 8
separate registers for both operands. Then it ORs the 8 bytes into a single 64
bit number. Then, it executes the 64 bit operation. And lastly, it splits the
64 bits result into 8 bytes into 8 different registers, and stores this 8 bytes
one after the other.
When I saw this I was impressed that that utterly bloated code did run faster
than a hastyly written assembly program I did in 10 minutes. Obviously I didn’t
take any pipeline turbulence into account and my program was slower. When I did
take pipeline turbulence into account, I managed to write a program that runs
several times faster than the bloated code.
You realize that for the example above, instead of
1) Load 64 bits into a register (2 operations)
2) Do the operation
3) Store the result
We have 2 loads, and 1 operation + a store. 4 instructions compared to 46
operations for the « gcc way » (16 loads of a byte, 14 x 2 OR operations and 8
shifts to split the result and 8 stores of a byte each.
I think this is a BUG, but I’m still not convinced that it is one, and I do
not have a clue WHY you do this.
Is here anyone doing the riscv backend? This happens only with -O3 by the way
Sample code:
#define ACCUM_MENGTH 9
#define WORDSIZE 64
Typedef struct {
Int sign, exponent;
Long long mantissa[ACCUM_LENGTH];
} QfloatAccum,*QfloatAccump;
void shup1(QfloatAccump x)
{
QELT newbits,bits;
int i;
bits = x->mantissa[ACCUM_LENGTH] >> (WORDSIZE-1);
x->mantissa[ACCUM_LENGTH] <<= 1;
for( i=ACCUM_LENGTH-1; i>0; i-- ) {
newbits = x->mantissa[i] >> (WORDSIZE - 1);
x->mantissa[i] <<= 1;
x->mantissa[i] |= bits;
bits = newbits;
}
x->mantissa[0] <<= 1;
x->mantissa[0] |= bits;
}
Please point me to the right person. Thanks
Re: [PATCH v5 2/5] libcpp: add a function to determine UTF-8 validity of a C string
On Wed, Jan 25, 2023 at 4:09 PM Ben Boeckel via Gcc wrote: > > This simplifies the interface for other UTF-8 validity detections when a > simple "yes" or "no" answer is sufficient. > > libcpp/ > > * charset.cc: Add `_cpp_valid_utf8_str` which determines whether > a C string is valid UTF-8 or not. > * internal.h: Add prototype for `_cpp_valid_utf8_str`. > > Signed-off-by: Ben Boeckel [going through patches in patchwork] What's the status of this patch; did this ever get committed? I see that Jason preapproved this via his review of "[PATCH v3 2/3] libcpp: add a function to determine UTF-8 validity of a C string" Thanks Dave
Re: [PATCH v5 2/5] libcpp: add a function to determine UTF-8 validity of a C string
On 10/23/23 11:16, David Malcolm wrote: On Wed, Jan 25, 2023 at 4:09 PM Ben Boeckel via Gcc wrote: This simplifies the interface for other UTF-8 validity detections when a simple "yes" or "no" answer is sufficient. libcpp/ * charset.cc: Add `_cpp_valid_utf8_str` which determines whether a C string is valid UTF-8 or not. * internal.h: Add prototype for `_cpp_valid_utf8_str`. Signed-off-by: Ben Boeckel [going through patches in patchwork] What's the status of this patch; did this ever get committed? It was superseded. Jason
Re: [PATCH v5 2/5] libcpp: add a function to determine UTF-8 validity of a C string
On Mon, 2023-10-23 at 11:24 -0400, Jason Merrill wrote: > On 10/23/23 11:16, David Malcolm wrote: > > On Wed, Jan 25, 2023 at 4:09 PM Ben Boeckel via Gcc > > wrote: > > > > > > This simplifies the interface for other UTF-8 validity detections > > > when a > > > simple "yes" or "no" answer is sufficient. > > > > > > libcpp/ > > > > > > * charset.cc: Add `_cpp_valid_utf8_str` which determines > > > whether > > > a C string is valid UTF-8 or not. > > > * internal.h: Add prototype for `_cpp_valid_utf8_str`. > > > > > > Signed-off-by: Ben Boeckel > > > > [going through patches in patchwork] > > > > What's the status of this patch; did this ever get committed? > > It was superseded. Thanks; closed out in patchwork. Dave
Inquiry about ARM gcc5 CVE-2023-4039 Patch
Dear arms, I hope this message finds you well. I am writing to inquire about the issue of ARM gcc5 CVE-2023-4039. According to the advisory on GitHub (https://github.com/metaredteam/external-disclosures/security/advisories/GHSA-x7ch-h5rf-w2mf), this bug affects versions from 5.4.0 to the trunk as of May 15, 2023. However, I noticed that currently, patches are only provided for gcc7 and above, as per the information available on the ARM Security Center (https://developer.arm.com/Arm%20Security%20Center/GCC%20Stack%20Protector%20Vulnerability%20AArch64). Given the potential impact of this vulnerability, I am particularly interested in a patch for gcc5. Could you please provide information on whether a patch for gcc5 is available or planned? If not, could you suggest any possible workarounds or mitigation strategies for systems that are currently using gcc5? I appreciate your attention to this matter and look forward to your response. Best regards,
