[Bug tree-optimization/114277] New: Missed optimization: x*(x||b) => x

[Bug tree-optimization/114277] New: Missed optimization: x*(x||b) => x

[652023330028 at smail dot nju.edu.cn]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

            Bug ID: 114277
           Summary: Missed optimization: x*(x||b) => x
           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 noticed that the code below can be optimized as stated in the title
(x*(x||b) => x), but gcc -O3 missed it.

https://godbolt.org/z/W8xYrGdej

int a,b;
void func(int x){
    a=x*(x||b);
}

GCC -O3:
func(int):
        mov     eax, edi
        or      eax, DWORD PTR b[rip]
        mov     eax, 0
        cmove   edi, eax
        mov     DWORD PTR a[rip], edi
        ret

Expected code:
func(int):
        mov     DWORD PTR a[rip], edi
        ret

Surprisingly, GCC optimizes as expected for the following slightly more complex
code:
int c;
void func2(int x){
    a=x*(x||(b&&c));
}
func2(int):
        mov     DWORD PTR a[rip], edi
        ret

Thank you very much for your time and effort! We look forward to hearing from
you.

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.5
   Last reconfirmed|                            |2024-03-08
            Summary|Missed optimization:        |[11/12/13/14 Regression]
                   |x*(x||b) => x               |Missed optimization:
                   |                            |x*(x||b) => x
      Known to fail|                            |8.1.0
      Known to work|                            |7.5.0
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
In GCC 7, before PRE we had:
```
  # iftmp.0_3 = PHI <_8(3), 1(5)>
  _2 = iftmp.0_3 * x_4(D);
```

Which was able to optimized by PRE to:
```
  _9 = x_4(D) * _8;

  <bb 4> [100.00%]:
  # iftmp.0_3 = PHI <_8(3), 1(2)>
  # prephitmp_10 = PHI <_9(3), x_4(D)(2)>
  a = prephitmp_10;
```

Which is how GCC 7 was able to optimize it.

In GCC8+, reassociatation takes:
```
  <bb 2> [local count: 1073741825]:
  if (x_4(D) != 0)
    goto <bb 4>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 536870912]:
  b.1_1 = b;
  _7 = b.1_1 != 0;
  _8 = (int) _7;

  <bb 4> [local count: 1073741825]:
  # iftmp.0_3 = PHI <_8(3), 1(2)>
  _2 = iftmp.0_3 * x_4(D);
```

Into:
```
  _9 = x_4(D) | b.1_1;
  _10 = _9 != 0;
  _7 = b.1_1 != 0;
  _11 = (int) _10;
  _8 = (int) _7;
  _2 = x_4(D) * _11;
```

Which no longer can be optimized to just x_4(D).

Maybe:
(simplify
 (mult:c @0 (convert? (ne (bit_ior:c @0 @1) integer_zero_p)))
 @0)

Like similarly was done for  `a * !a` just recently. Note this won't catch all
cases though as @0 be deep in the bit_ior chain but it will catch some.

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[law at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org,
                   |                            |rzinsly at ventanamicro dot com

--- Comment #2 from Jeffrey A. Law <law at gcc dot gnu.org> ---
The other approach we could take (and which I think may have certain
advantages) would be to first realize this is a multiplication by a boolean
(0/1) value.  That's just a conditional move.  If we then rewrote as a
conditional move there's a reasonable chance we'd be able to further simplify.

The biggest problem with this approach is if we're aggressively transforming
into  conditional moves in gimple, the expanders will need improvement,
particularly on targets that don't have conditional moves.

Raphael has a TODO in this space.   He may have further thoughts.

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[rzinsly at ventanamicro dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

--- Comment #3 from Raphael M Zinsly <rzinsly at ventanamicro dot com> ---
Created attachment 57670
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57670&action=edit
proposed patch

I created this patch using the approach Jeff mentioned, I tested and it fixes
this bug.

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Raphael M Zinsly from comment #3)
> Created attachment 57670 [details]
> proposed patch
> 
> I created this patch using the approach Jeff mentioned, I tested and it
> fixes this bug.

As I mentioned in the other issue, there is an open question about which is
more Canonical.

I don't have this one listed on
https://gcc.gnu.org/wiki/GimpleCanonical#preview yet but I will add it. Because
there are 3 different ways of representing it.

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Thinking about this a little more.

((convert)boolean)*a is not Canonical

But `boolean?a:0` is. Due to one expression vs 2.

But `zero_one * a` is still Canonical if there is no cast from the boolean
type.

That will fix this issue but not the other.

[Bug tree-optimization/114277] [11/12/13/14 Regression] Missed optimization: x*(x||b) => x

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114277

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I will implement this part of the Canonicalization .