[Bug tree-optimization/111560] New: Missed optimization of available expression

[Bug tree-optimization/111560] New: Missed optimization of available expression

[652023330028 at smail dot nju.edu.cn]

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.

[Bug tree-optimization/111560] Missed optimization of available expression

[pinskia at gcc dot gnu.org]

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.

[Bug tree-optimization/111560] Missed optimization of available expression

[pinskia at gcc dot gnu.org]

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. ***

[Bug tree-optimization/111560] Missed optimization of available expression

[pinskia at gcc dot gnu.org]

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. ***

[Bug tree-optimization/111560] Missed optimization of available expression

[652023330028 at smail dot nju.edu.cn]

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 .

[Bug tree-optimization/111560] Missed optimization of available expression

[pinskia at gcc dot gnu.org]

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.

[Bug tree-optimization/111560] Missed optimization of available expression

[rguenth at gcc dot gnu.org]

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.