[Bug tree-optimization/105832] New: Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[Bug tree-optimization/105832] New: Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[theodort at inf dot ethz.ch]

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

            Bug ID: 105832
           Summary: Dead Code Elimination Regression at -O3 (trunk vs.
                    12.1.0)
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: theodort at inf dot ethz.ch
  Target Milestone: ---

cat case.c #2
void foo(void);

static struct {
    short a;
    char b;
} c;

static char d;

int main() {
    char g = c.b > 4U ? c.b : c.b << 2;
    for (int h = 0; h < 5; h++) {
        d = (g >= 2 || 1 >> g) ? g : g << 1;
        if (d && 1 == g)
            foo();
        c.a = 0;
    }
}

`gcc-1982fe2692b6c3b7f969ffc4edac59f9d4359e91 (trunk) -O3` can not eliminate
`foo` but `gcc-releases/gcc-12.1.0 -O3` can.

`gcc-1982fe2692b6c3b7f969ffc4edac59f9d4359e91 (trunk) -O3 -S -o /dev/stdout
case.c`
--------- OUTPUT ---------
main:
.LFB0:
        .cfi_startproc
        movsbl  c+2(%rip), %edx
        movl    %edx, %eax
        sall    $2, %edx
        cmpb    $5, %al
        cmovb   %edx, %eax
        cmpb    $1, %al
        jle     .L3
.L13:
        xorl    %eax, %eax
        movw    %ax, c(%rip)
        xorl    %eax, %eax
        ret
.L3:
        movsbl  %al, %edx
        addl    %edx, %edx
        testb   %al, %al
        cmove   %eax, %edx
        testb   %dl, %dl
        je      .L13
        subb    $1, %al
        jne     .L13
        pushq   %rbx
        .cfi_def_cfa_offset 16
        .cfi_offset 3, -16
        movl    $5, %ebx
.L6:
        call    foo
        movw    $0, c(%rip)
        subl    $1, %ebx
        jne     .L6
        xorl    %eax, %eax
        popq    %rbx
        .cfi_def_cfa_offset 8
        ret
---------- END OUTPUT ---------


`gcc-releases/gcc-12.1.0 -O3 -S -o /dev/stdout case.c`
--------- OUTPUT ---------
main:
.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        movw    %ax, c(%rip)
        xorl    %eax, %eax
        ret
---------- END OUTPUT ---------


Bisects to:
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=a1c9f779f75283427316b5c670c1e01ff8ce9ced

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Dead Code Elimination       |[13 Regression] Dead Code
                   |Regression at -O3 (trunk    |Elimination Regression at
                   |vs. 12.1.0)                 |-O3 (trunk vs. 12.1.0)
   Last reconfirmed|                            |2022-06-13
                 CC|                            |rguenth at gcc dot gnu.org
   Target Milestone|---                         |13.0
           Keywords|                            |missed-optimization
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  GCC 12:

t.c:12:23: optimized: Unswitching loop on condition: if (iftmp.0_9 <= 1)

t.c:12:23: optimized: Unswitching loop on condition: if (iftmp.0_9 == 1)

t.c:12:23: optimized: Unswitching loop on condition: if (iftmp.1_10 != 0)

t.c:12:23: optimized: Unswitching loop on condition: if (iftmp.1_10 != 0)

and trunk:

t.c:12:23: optimized: unswitching loop 1 on ‘if’ with condition: iftmp.0_9 <= 1
t.c:12:23: optimized: unswitching loop 1 on ‘if’ with condition: iftmp.1_10 !=
0
t.c:12:23: optimized: unswitching loop 1 on ‘if’ with condition: iftmp.0_9 == 1

somehow trunk doesn't consider the 2nd iftmp.1_10 != 0 condition.

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Investigating.

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So the difference boils down to GCC 12 ending up with

if (iftmp.0_9 == 1)
 {
   if (iftmp.1_10 != 0)
     {
       loop with call to foo ();
     }
 }

while the new unswitching code swaps these and ends up with

if (iftmp.1_10 != 0)
 {
   if (iftmp.0_9 == 1)
     {
       loop with call to foo ();
     }
 }

the old code also created one pointless unreachable loop copy.  GCC 12
manages to elide the loop calling foo() in thread2 after fre5.

There's nothing wrong with unswitching here I think - we're at most unlucky
with the order of unswitchings (but that might change from current 'random'
to a cost based order).

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |needs-bisection

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Raising --param max-jump-thread-duplication-stmts from its default 15 to 17
fixes the issue.  So the issue is slightly different accounting of sizes in the
threading code and slightly different IL (though it is smaller).  Quite
possibly the bisection wasn't accurate.

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
With r13-3897-gbe2c74fdcd0e8d66 get:
gcc pr105832.c -c -O3 -fdump-tree-optimized=/dev/stdout --param
max-jump-thread-duplication-stmts=17


;; Function main (main, funcdef_no=0, decl_uid=2741, cgraph_uid=1,
symbol_order=2) (executed once)

int main ()
{
  <bb 2> [local count: 178992760]:
  c.a = 0;
  return 0;

}

before the revision I was:

;; Function main (main, funcdef_no=0, decl_uid=2741, cgraph_uid=1,
symbol_order=2) (executed once)

Removing basic block 5
int main ()
{
  char _1;
  unsigned char _2;
  char iftmp.0_11;

  <bb 2> [local count: 178992758]:
  _1 = c.b;
  _2 = (unsigned char) _1;
  if (_2 > 4)
    goto <bb 4>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 89496379]:
  iftmp.0_11 = _1 << 2;

  <bb 4> [local count: 178992760]:
  c.a = 0;
  return 0;

}

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #5)
> With r13-3897-gbe2c74fdcd0e8d66 get:
> gcc pr105832.c -c -O3 -fdump-tree-optimized=/dev/stdout --param
> max-jump-thread-duplication-stmts=17
> 
> 
> ;; Function main (main, funcdef_no=0, decl_uid=2741, cgraph_uid=1,
> symbol_order=2) (executed once)
> 
> int main ()
> {
>   <bb 2> [local count: 178992760]:
>   c.a = 0;
>   return 0;
> 
> }
> 
> before the revision I was:
> 
> ;; Function main (main, funcdef_no=0, decl_uid=2741, cgraph_uid=1,
> symbol_order=2) (executed once)
> 
> Removing basic block 5
> int main ()
> {
>   char _1;
>   unsigned char _2;
>   char iftmp.0_11;
> 
>   <bb 2> [local count: 178992758]:
>   _1 = c.b;
>   _2 = (unsigned char) _1;
>   if (_2 > 4)
>     goto <bb 4>; [50.00%]
>   else
>     goto <bb 3>; [50.00%]
> 
>   <bb 3> [local count: 89496379]:
>   iftmp.0_11 = _1 << 2;
> 
>   <bb 4> [local count: 178992760]:
>   c.a = 0;
>   return 0;
> 
> }

That's still without a call to foo ()?

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[marxin at gcc dot gnu.org]

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

--- Comment #7 from Martin Liška <marxin at gcc dot gnu.org> ---
With --param=max-jump-thread-duplication-stmts=17 -O3 the call to 'foo' is gone
since r8-910-g10bc8017a3028c29.

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2022-10-19 00:00:00         |2023-2-21

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Re-confirmed.

[Bug tree-optimization/105832] [13 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[law at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org
           Priority|P3                          |P2

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.0                        |13.2

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.1 is being released, retargeting bugs to GCC 13.2.

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I think the simple way of fixing this is optimizing:
```
bool f(int g)
{
return (1 >> g) != 0;
}
```
into
```
bool f0(int g)
{
return g == 0;
}
```

In threadfull1 (before vrp1) we have:
```
  <bb 5> [local count: 894749065]:
  if (iftmp.0_6 <= 1)
    goto <bb 6>; [41.00%]
  else
    goto <bb 8>; [59.00%]

  <bb 6> [local count: 366847113]:
  _3 = (int) iftmp.0_6;
  _4 = 1 >> _3;
  if (_4 == 0)
    goto <bb 7>; [50.00%]
  else
    goto <bb 8>; [50.00%]

  <bb 7> [local count: 183423557]:
  iftmp.1_12 = iftmp.0_6 << 1;

  <bb 8> [local count: 894749065]:
  # iftmp.1_7 = PHI <iftmp.1_12(7), iftmp.0_6(5), iftmp.0_6(6)>
```
if we optimize the bb6 to:
```
  if (iftmp.0_6 != 0)
    goto <bb 7>; [50.00%]
  else
    goto <bb 8>; [50.00%]
```
We should be able to ifcombine the 2 GIMPLE to just:
iftmp.0_6 != 0 && iftmp.0_6 <= 1

Which then will unswitch correctly ...

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[law at gcc dot gnu.org]

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

--- Comment #11 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Looks viable to me.  Are you thinking match.pd?

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.2                        |13.3

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #11)
> Looks viable to me.  Are you thinking match.pd?

Yes I was thinking that. I should note that LLVM does that transformation too.

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.2 is being released, retargeting bugs to GCC 13.3.

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #10)
> I think the simple way of fixing this is optimizing:
> ```
> bool f(int g)
> {
> return (1 >> g) != 0;
> }
> ```
> into
> ```
> bool f0(int g)
> {
> return g == 0;
> }
> ```

I am going to do the above.

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[pinskia at gcc dot gnu.org]

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

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So there is a pattern for:
/* Simplify ((C <</>> x) & D) != 0 where C and D are power of two constants,
   either to false if D is smaller (unsigned comparison) than C, or to
   x == log2 (D) - log2 (C).  Similarly for right shifts.  */

But in this case C is 1 and (D is 1 but removed as 1>>N is either [0,1]). 
So we just need to add one for this.

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[pinskia at gcc dot gnu.org]

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

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 55833
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55833&action=edit
Patch which I am testing

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2023-Septemb
                   |                            |er/629172.html
           Keywords|                            |patch

--- Comment #17 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed up patch posted:
https://gcc.gnu.org/pipermail/gcc-patches/2023-September/629172.html

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #18 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:b34f373635635fa331d2803d9232b3cfd4fd4fd1

commit r14-3719-gb34f373635635fa331d2803d9232b3cfd4fd4fd1
Author: Andrew Pinski <apinski@marvell.com>
Date:   Sun Sep 3 06:04:41 2023 +0000

    MATCH: Transform `(1 >> X) !=/== 0` into `X ==/!= 0`

    We currently have a pattern for handling `(C >> X) & D == 0`
    but if C is 1 and D is 1, the `& 1` might have been removed.

    gcc/ChangeLog:

            PR tree-optimization/105832
            * match.pd (`(1 >> X) != 0`): New pattern

    gcc/testsuite/ChangeLog:

            PR tree-optimization/105832
            * gcc.dg/tree-ssa/pr105832-1.c: New test.
            * gcc.dg/tree-ssa/pr105832-2.c: New test.
            * gcc.dg/tree-ssa/pr105832-3.c: New test.

[Bug tree-optimization/105832] [13/14 Regression] Dead Code Elimination Regression at -O3 (trunk vs. 12.1.0)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.3                        |14.0
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #19 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed.