[Bug tree-optimization/108360] New: Dead Code Elimination Regression at -Os (trunk vs. 12.2.0)

[Bug tree-optimization/108360] New: Dead Code Elimination Regression at -Os (trunk vs. 12.2.0)

[yann at ywg dot ch]

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

            Bug ID: 108360
           Summary: Dead Code Elimination Regression at -Os (trunk vs.
                    12.2.0)
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: yann at ywg dot ch
  Target Milestone: ---

Created attachment 54235
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54235&action=edit
case.c as file

cat case.c #321
static short b, c;
unsigned char e;
char f;
void foo();
short(a)(short h, short i) { return h + i; }
static short(d)(short h, int i) { return h >= 32 || h > 7 >> i ? h : h << i; }
unsigned g(short h, short i) { return h + i; }
int main() {
  short j, k = -1;
  c = a(0 >= b, k);
  f = c <= 0xD315BEF1;
  e = f << 4;
  j = d(e, 5);
  if (3 >= g(j == b, k))
    foo();
  b = 0;
}

`gcc-cb93c5f8008b95743b741d6f1842f9be50c6985c (trunk) -Os` can not eliminate
`foo` but `gcc-releases/gcc-12.2.0 -Os` can.

`gcc-cb93c5f8008b95743b741d6f1842f9be50c6985c (trunk) -Os -S -o /dev/stdout
case.c`
--------- OUTPUT ---------
main:
.LFB3:
        .cfi_startproc
        movw    b(%rip), %cx
        xorl    %edx, %edx
        testw   %cx, %cx
        setle   %dl
        movl    %edx, %eax
        movb    %dl, f(%rip)
        sall    $4, %eax
        movb    %al, e(%rip)
        movzbl  %al, %eax
        testw   %dx, %dx
        jne     .L4
        sall    $5, %eax
.L4:
        cmpw    %ax, %cx
        jne     .L7
        pushq   %rax
        .cfi_def_cfa_offset 16
        xorl    %eax, %eax
        call    foo
        xorl    %eax, %eax
        movw    $0, b(%rip)
        popq    %rdx
        .cfi_def_cfa_offset 8
        ret
.L7:
        movw    $0, b(%rip)
        xorl    %eax, %eax
        ret
---------- END OUTPUT ---------


`gcc-releases/gcc-12.2.0 -Os -S -o /dev/stdout case.c`
--------- OUTPUT ---------
main:
.LFB3:
        .cfi_startproc
        xorl    %eax, %eax
        cmpw    $0, b(%rip)
        movw    $0, b(%rip)
        setle   %al
        movb    %al, f(%rip)
        sall    $4, %eax
        movb    %al, e(%rip)
        xorl    %eax, %eax
        ret
---------- END OUTPUT ---------


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

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
            Summary|Dead Code Elimination       |[13 Regression] Dead Code
                   |Regression at -Os (trunk    |Elimination Regression at
                   |vs. 12.2.0)                 |-Os since
                   |                            |r13-2048-g418b71c0d535bf
   Last reconfirmed|                            |2023-01-10
     Ever confirmed|0                           |1
   Target Milestone|---                         |13.0
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |sayle at gcc dot gnu.org

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So, this used to be optimized out during vrp2, but I'm surprised how the ranger
could figure it out.
It is true that foo is never called.  If b is initially <= 0 (that is actually
the case when running the program), then c is 0, f is 1, e is 16, j is 16, j==b
is 0 and so
g(j==b,k) is -1U; if b is initially > 0, then c is -1, f, e and j are 0, j==b
is 0 and so g(j==b,k) is also -1U.
I'm just surprised how GCC 12 ranger or old style VRP could figure that out
though.
Because when it only considers variable ranges, c is ]-1,0], f is [0,1], e and
j are [0,16] or [0,0] U [16,16] but that doesn't imply that b (VARYING) == j is
actually false or true.

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Seems it happens even with
short b;
static short c;
unsigned char e;
char f;
void foo();
short(a)(short h, short i) { return h + i; }
static short(d)(short h, int i) { return (h >= 32 || h > (7 >> i)) ? h : h <<
i; }
unsigned g(short h, short i) { return h + i; }
int main() {
  short j, k = -1;
  c = a(0 >= b, k);
  f = c <= 0xD315BEF1;
  e = f << 4;
  j = d(e, 5);
  if (3 >= g(j == b, k))
    foo();
  b = 32;
}
where we can't assume anything about b's value initially.
Still in GCC 12 we decide to thread jump it based on whether e (h in inlined d)
is 0 or non-0 - h >= 32 is based on ranges clearly always false and as e has
[0, 16] range, h > 0 and h != 0 are the same thing, if h != 0, then d returns
h, otherwise h << 5.  Later on we correctly figure out that if h == 0, then h
<< 5 is 0.  But what I really don't understand how threadfull1 in that case
decided that foo will not be called.

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The first difference with r13-2048 is during fre3:
@@ -210,7 +210,7 @@ marking outgoing edge 6 -> 1 executable
 RPO iteration over 5 blocks visited 5 blocks in total discovering 5 executable
blocks iterating 1.0 times, a block was visited max. 1 times
 RPO tracked 25 values available at 18 locations and 25 lattice elements
 Replaced (int) _6 with _7 in all uses of _24 = (int) _6;
-gimple_simplified to if (_6 == 0)
+gimple_simplified to if (_22 < 0)
 Replaced (short int) _6 with h_23 in all uses of _25 = (short int) _6;
 Removing dead stmt _25 = (short int) _6;
 Removing dead stmt _24 = (int) _6;
@@ -259,7 +259,7 @@ int main ()
   _7 = (int) _6;
   # RANGE [irange] short int [-INF, +INF] NONZERO 0x10
   h_23 = (short int) _6;
-  if (_6 == 0)
+  if (_22 < 0)
     goto <bb 3>; [50.00%]
   else
     goto <bb 4>; [50.00%]
Given:
  _3 = _22 >= 0;
  _4 = (char) _3;
  f.5_5 = (unsigned char) _3;
  _6 = f.5_5 << 4;
  h_23 = (short int) _6;
and range of f.5_5 being [0, 1] that change is certainly correct.

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[amacleod at redhat dot com]

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

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
The IL is different in VRP2 between GCC12 and GCC13.  IN GCC 12 I see:

  <bb 2> [local count: 1073741824]:
  b.2_1 = b;
  _2 = b.2_1 <= 0;
  h.0_20 = (unsigned short) _2;
  _21 = h.0_20 + 65535;
  _22 = (short int) _21;
  _3 = _22 >= 0;
  _4 = (char) _3;
  f = _4;
  f.5_5 = (unsigned char) _3;
  _6 = f.5_5 << 4;
  e = _6;
  h_23 = (short int) _6;
  if (_6 == 0)
    goto <bb 5>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 805306368]:
  _8 = b.2_1 == h_23;

Global ranges for bb2 are:
_4 : char [0, 1]
f.5_5 : unsigned char [0, 1]
_6 : unsigned char [0, 0][16, 16]
h.0_20 : unsigned short [0, 1]
_21 : unsigned short [0, 0][+INF, +INF]
_22 : short int [-1, 0]

Looking at what ranger calculates for the edge 2->3 based on _6 having to be 0:

2->3  (F) b.2_1 :       short int [-INF, 0]
2->3  (F) _2 :  _Bool [1, 1]
2->3  (F) _3 :  _Bool [1, 1]
2->3  (F) _4 :  char [1, 1]
2->3  (F) f.5_5 :       unsigned char [1, 1]
2->3  (F) _6 :  unsigned char [16, 16]
2->3  (F) h.0_20 :      unsigned short [1, 1]
2->3  (F) _21 :         unsigned short [0, 0]
2->3  (F) _22 :         short int [0, 0]
2->3  (F) h_23 :        short int [16, 16]

It can determine that h_23 is [16,16] and therefore _8 is always false.  and
when you use _8 = [0, 0]  the condition leading to the call can never be true
so it's eliminated.

The code sequence at -Os is quite different coming into VRP2 in GCC13.  It
involves a PHI node and the condition uses _21 == -1  instead of _6 == 0.  
This cahnges what we can evaluate going out, and when we get to valuation of
_8, it sees:

_8 = b.2_1 == iftmp.8_28;

and iftmp.8_28 is evaluated as [0, 0][16, 16][512, 512]

Because 0 hasnt been eliminated, we cant fold the condition.

We do still get this at -O2... just not at -Os.

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
The key change is that condition:
   _6 = f.5_5 << 4;
    e = _6;
    h_23 = (short int) _6;

    if (_21 == -1)
      goto <bb 3>; [50.00%]
    else
      goto <bb 4>; [50.00%]

On the false edge, we lose the ability to determine that h_23 is [16,16], and
instead, it remains [0,0][16,16]..    that causes us to not be able to
eliminate the branch

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[amacleod at redhat dot com]

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

--- Comment #6 from Andrew Macleod <amacleod at redhat dot com> ---
and VRP1 turned that 
if (_21 < 0)
into 
if (_21 == -1)

So yes, that was a correct transformation in FRE3, but the side effect is we
lose the ability to look back and determine better ranges for _6 and h_23 as _6
is no longer part of the branch

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
I now see the following IL into the last VRP pass

  <bb 2> [local count: 1073741824]:
  b.2_1 = b;
  _2 = b.2_1 <= 0;
  h.0_19 = (unsigned short) _2;
  _20 = h.0_19 + 65535;
  _21 = (short int) _20;
  _3 = _21 >= 0;
  _4 = (char) _3;
  f = _4;
  f.5_5 = (unsigned char) _3;
  _6 = f.5_5 << 4;
  e = _6;
  _23 = (short int) _3;
  _26 = _23 << 4;
  _8 = b.2_1 == _26;  [0,1]
  h_15 = (short int) _8; [0,1]
  _22 = h_15 + -1;  [-1,0]
  _18 = (unsigned int) _22;
  if (_18 <= 3) // we could substitute (b.2_1 == _26) here
    goto <bb 3>; [33.00%]
  else
    goto <bb 4>; [67.00%]

  <bb 3> [local count: 354334800]:
  foo ();

the last branch could be simplified by VRP, first we fail to replace
it by _18 == 0 which would then fold to _22 == 0 and then further to
the suggested compare.

Note I see -O2 and -O1 optimizing this just fine.  DOM2 threads a jump
here but some differences start earlier already.  It really looks some
phase-ordering bad luck triggers here, mainly triggered by early inlining
differences.

[Bug tree-optimization/108360] [13 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[law at gcc dot gnu.org]

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

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

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

[Bug tree-optimization/108360] [13/14 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[rguenth at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/108360] [13/14 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[rguenth at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/108360] [13/14 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is the example code which is not optimized at the gimple level (but is at
the RTL level):
```
void gg();
void hh();
void f1(int a, int b)
{
  short t = a == b;
  t -= 1;
  unsigned t1 = t;
  if (t1 <= 3)
    gg();
  else
    hh();
}
// Even the simplier example:
void f2(int a, int b)
{
  unsigned t = a == b;
  t = -t;
  unsigned t1 = t;
  if (t1 <= 3)
    gg();
  else
    hh();
}
```

[Bug tree-optimization/108360] [13/14 Regression] Dead Code Elimination Regression at -Os since r13-2048-g418b71c0d535bf

[pinskia at gcc dot gnu.org]

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

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a patch which gets us to:
```
  short int b.2_1;
...
  b.2_1 = b;
  _2 = b.2_1 <= 0;
  _4 = (char) _2;
  f = _4;
  f.5_5 = (unsigned char) _2;
  _6 = f.5_5 << 4;
  e = _6;
  _19 = b.2_1 <= 0;
  _7 = (short int) _19;
  _21 = _7 << 4;
  if (b.2_1 == _21)

```
Which is closer.

```
int f(short b)
{
  auto _19 = b <= 0;
  auto _7 = (short int) _19;
  auto _21 = _7 << 4;
  return b == _21;
}
```
is just `return false;` as _21's range is `[0,4]` but it is only 0 when `b > 0`

And then maybe:
(simplify
 (eq:c @0 (rshift (convert (le @0 integer_zero_p)) INTEGER_CST@1))
 (if (wi::to_wide(@1) < element_precision (TREE_TYPE (@0)) - 1)
  ( { false_value; } ))

Is this worth this pattern, I don't know ...