public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/111560] New: Missed optimization of available expression
@ 2023-09-24 3:34 652023330028 at smail dot nju.edu.cn
2023-09-24 3:39 ` [Bug tree-optimization/111560] " pinskia at gcc dot gnu.org
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: 652023330028 at smail dot nju.edu.cn @ 2023-09-24 3:34 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
Bug ID: 111560
Summary: Missed optimization of available expression
Product: gcc
Version: 14.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: 652023330028 at smail dot nju.edu.cn
Target Milestone: ---
Hello, we found some optimizations (regarding Available Expression) that GCC
may have missed. We would greatly appreicate if you can take a look and let us
know what you think.
Here are three examples.
Example 1:
https://godbolt.org/z/eYcWocsPf
Given the following code:
```c++
int test()
{
int a,b,c,d,e,f,g;
cin>>a>>b>>c>>d>>g;
e=a+b+c; //line 5
f=d+b+c; //"b+c" can be replaced with the value at line 5
cout<<e<<f;
return 0;
}
```
We note that `b+c` at line 6 in the test code can be replaced with the value at
line 5, but gcc-trunk -O3 does not:
```asm
test():
push rbx
mov edi, OFFSET FLAT:_ZSt3cin
sub rsp, 32
lea rsi, [rsp+12]
call std::basic_istream<char, std::char_traits<char>
>::operator>>(int&)
lea rsi, [rsp+16]
mov rdi, rax
call std::basic_istream<char, std::char_traits<char>
>::operator>>(int&)
lea rsi, [rsp+20]
mov rdi, rax
call std::basic_istream<char, std::char_traits<char>
>::operator>>(int&)
lea rsi, [rsp+24]
mov rdi, rax
call std::basic_istream<char, std::char_traits<char>
>::operator>>(int&)
lea rsi, [rsp+28]
mov rdi, rax
call std::basic_istream<char, std::char_traits<char>
>::operator>>(int&)
mov esi, DWORD PTR [rsp+16]
mov ebx, DWORD PTR [rsp+24]
mov edi, OFFSET FLAT:_ZSt4cout
mov eax, DWORD PTR [rsp+20]
add ebx, esi
add esi, DWORD PTR [rsp+12]
add esi, eax
add ebx, eax
call std::basic_ostream<char, std::char_traits<char>
>::operator<<(int)
mov esi, ebx
mov rdi, rax
call std::basic_ostream<char, std::char_traits<char>
>::operator<<(int)
add rsp, 32
xor eax, eax
pop rbx
ret
```
Example 2:
https://godbolt.org/z/o61sx6dGh
Given the following code:
```c++
int var_13; int var_14;
void test(int var_0, int var_4, int var_5) {
var_13 = var_0 + var_4 + var_5; //line 3
var_14 = var_4 + var_5; //"var_4 + var_5" can be replaced with the value
at line 3
}
```
We note that `var_4 + var_5` at line 4 in the test code can be replaced with
the value at line 3, but gcc-trunk -O3 does not:
```asm
test(int, int, int):
add edi, esi
add esi, edx
add edi, edx
mov DWORD PTR var_14[rip], esi
mov DWORD PTR var_13[rip], edi
ret
var_14:
.zero 4
var_13:
.zero 4
```
Example 3:
https://godbolt.org/z/caYT9E6Mz
Similar to example 2, but this is an example that might involve shifting
operations:
```c++
int var_14,var_27;
void test(int var_1, int var_3) {
var_14 = var_1 + var_1;
var_27 = var_3 + var_1 + var_1;
}
```
```asm
test(int, int):
lea eax, [rdi+rdi]
mov DWORD PTR var_14[rip], eax
lea eax, [rsi+rdi*2]
mov DWORD PTR var_27[rip], eax
ret
var_27:
.zero 4
var_14:
.zero 4
```
Thank you very much for your time and effort! We look forward to hearing from
you.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/111560] Missed optimization of available expression
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
@ 2023-09-24 3:39 ` pinskia at gcc dot gnu.org
2023-09-24 3:42 ` pinskia at gcc dot gnu.org
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-09-24 3:39 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |missed-optimization
Severity|normal |enhancement
--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The problem is in this case:
e=a+b+c; //line 5
f=d+b+c; //"b+c" can be replaced with the value at line 5
at the gimple level, b+c could introduce an signed integer overflow. And we
don't want to introduce that.
If you had used unsigned, rather than int, the optimization would have been
done as we do reassociate unsigned integers just fine.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/111560] Missed optimization of available expression
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
2023-09-24 3:39 ` [Bug tree-optimization/111560] " pinskia at gcc dot gnu.org
@ 2023-09-24 3:42 ` pinskia at gcc dot gnu.org
2023-09-24 3:43 ` pinskia at gcc dot gnu.org
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-09-24 3:42 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 111561 has been marked as a duplicate of this bug. ***
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/111560] Missed optimization of available expression
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
2023-09-24 3:39 ` [Bug tree-optimization/111560] " pinskia at gcc dot gnu.org
2023-09-24 3:42 ` pinskia at gcc dot gnu.org
@ 2023-09-24 3:43 ` pinskia at gcc dot gnu.org
2023-09-24 4:01 ` 652023330028 at smail dot nju.edu.cn
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-09-24 3:43 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 111562 has been marked as a duplicate of this bug. ***
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/111560] Missed optimization of available expression
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
` (2 preceding siblings ...)
2023-09-24 3:43 ` pinskia at gcc dot gnu.org
@ 2023-09-24 4:01 ` 652023330028 at smail dot nju.edu.cn
2023-09-24 4:50 ` pinskia at gcc dot gnu.org
2023-09-24 6:51 ` rguenth at gcc dot gnu.org
5 siblings, 0 replies; 7+ messages in thread
From: 652023330028 at smail dot nju.edu.cn @ 2023-09-24 4:01 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
--- Comment #4 from Yi <652023330028 at smail dot nju.edu.cn> ---
(In reply to Andrew Pinski from comment #1)
> The problem is in this case:
> e=a+b+c; //line 5
> f=d+b+c; //"b+c" can be replaced with the value at line 5
>
> at the gimple level, b+c could introduce an signed integer overflow. And we
> don't want to introduce that.
>
>
> If you had used unsigned, rather than int, the optimization would have been
> done as we do reassociate unsigned integers just fine.
Thank you very much for your quick reply!
But example 1 in Bug 111561 does not seem to be well resolved.
https://godbolt.org/z/cM4n8qvrh
Given the following code:
```c++
extern unsigned var_26;
extern unsigned var_29;
void test(unsigned var_1, unsigned var_2, unsigned var_3) {
var_29 = (var_1 + var_2) ? var_1 : var_2;
var_26 = var_1 + (var_2 + var_3);
}
```
```asm
test(unsigned int, unsigned int, unsigned int):
mov eax, edi
add eax, esi
mov eax, edi
cmove eax, esi
add esi, edx
add esi, edi
mov DWORD PTR var_29[rip], eax
mov DWORD PTR var_26[rip], esi
ret
```
So does Bug 111562 .
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/111560] Missed optimization of available expression
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
` (3 preceding siblings ...)
2023-09-24 4:01 ` 652023330028 at smail dot nju.edu.cn
@ 2023-09-24 4:50 ` pinskia at gcc dot gnu.org
2023-09-24 6:51 ` rguenth at gcc dot gnu.org
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-09-24 4:50 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
See Also| |https://gcc.gnu.org/bugzill
| |a/show_bug.cgi?id=35288
--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Yi from comment #4)
Right there is another issue which this is a dup of though but I can't find it
right now. The problem is reassociation only partly solves the issues.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/111560] Missed optimization of available expression
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
` (4 preceding siblings ...)
2023-09-24 4:50 ` pinskia at gcc dot gnu.org
@ 2023-09-24 6:51 ` rguenth at gcc dot gnu.org
5 siblings, 0 replies; 7+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-24 6:51 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111560
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |rguenth at gcc dot gnu.org
Status|UNCONFIRMED |NEW
Ever confirmed|0 |1
Last reconfirmed| |2023-09-24
--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed. Simpler testcase:
int e,f;
void test(int a, int b, int c, int d)
{
e=a+b+c; //line 5
f=d+b+c; //"b+c" can be replaced with the value at line 5
}
it's as Andrew says plus re-associating for global optimal CSE is difficult,
imagine adding
g = a + b + d;
to the above. There's either a + b in common with e but then that breaks
commoning b + c in e and f or there is b + d in common with f also breaking
the other CSE.
Our re-association only produces a canonical order within a single expression.
That doesn't by design allow CSE of common subexpressions in other expressions.
I don't know of any work (paper) describing how to attack this global
optimization problem.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2023-09-24 6:51 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-24 3:34 [Bug tree-optimization/111560] New: Missed optimization of available expression 652023330028 at smail dot nju.edu.cn
2023-09-24 3:39 ` [Bug tree-optimization/111560] " pinskia at gcc dot gnu.org
2023-09-24 3:42 ` pinskia at gcc dot gnu.org
2023-09-24 3:43 ` pinskia at gcc dot gnu.org
2023-09-24 4:01 ` 652023330028 at smail dot nju.edu.cn
2023-09-24 4:50 ` pinskia at gcc dot gnu.org
2023-09-24 6:51 ` rguenth at gcc dot gnu.org
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).