[Bug tree-optimization/110891] New: [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[Bug tree-optimization/110891] New: [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[theodort at inf dot ethz.ch]

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

            Bug ID: 110891
           Summary: [14 Regression] Dead Code Elimination Regression since
                    r14-2674-gd0de3bf9175
           Product: gcc
           Version: 14.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: ---

https://godbolt.org/z/njdE3xof4

Given the following code:

void foo(void);
static int a, c = 7, d, o, q;
static int *b = &a, *f, *j = &d, *n = &c, *ae;
static short e, m;
static short *i = &e;
static char r;
void __assert_fail(char *, char *, int, char *) __attribute__((__noreturn__));
static const short g();
static void h();
static int *k(int) {
    (*i)++;
    *j ^= *b;
    return &a;
}
static void l(unsigned p) {
    int *aa = &o;
    h();
    o = 5 ^ g() && p;
    if (f == &d || f == &c || f == &a)
        ;
    else {
        foo();
        __assert_fail("", "", 3, __PRETTY_FUNCTION__);
    }
    *aa ^= *n;
    if (*aa)
        if (!(((p) >= 0) && ((p) <= 0))) {
            __builtin_unreachable();
        }
    k(p);
}
static const short g() { return q; }
static void h() {
    unsigned ag = c;
    d = ag > r ? ag : 0;
    ae = k(c);
    f = ae;
    if (ae == &d || ae == &c || ae == &a)
        ;
    else
        __assert_fail("", "", 4, __PRETTY_FUNCTION__);
}
int main() {
    l(a);
    m || (*b |= 64);
    *b &= 5;
}

gcc-trunk -O2 does not eliminate the call to foo:

main:
        subq    $8, %rsp
        movl    c(%rip), %eax
        movl    %eax, d(%rip)
        call    k.isra.0
        cmpq    $c, %rax
        movq    %rax, f(%rip)
        sete    %cl
        cmpq    $a, %rax
        sete    %dil
        cmpq    $d, %rax
        sete    %dl
        orb     %cl, %dl
        jne     .L4
        testb   %dil, %dil
        je      .L15
.L4:
        cmpq    $d, %rax
        je      .L6
        testb   %cl, %cl
        jne     .L6
        testb   %dil, %dil
        je      .L16
.L6:
        call    k.isra.0
        andl    $5, a(%rip)
        xorl    %eax, %eax
        addq    $8, %rsp
        ret
.L16:
        call    foo
        movl    $.LC0, %esi
        movl    $__PRETTY_FUNCTION__.1, %ecx
        movl    $3, %edx
        movq    %rsi, %rdi
        call    __assert_fail
.L15:
        movl    $.LC0, %esi
        movl    $__PRETTY_FUNCTION__.0, %ecx
        movl    $4, %edx
        movq    %rsi, %rdi
        call    __assert_fail

gcc-13.2.0 -O2 eliminates the call to foo:

main:
        subq    $8, %rsp
        movl    c(%rip), %eax
        movl    %eax, d(%rip)
        call    k.isra.0
        cmpq    $c, %rax
        movq    %rax, f(%rip)
        sete    %dl
        cmpq    $d, %rax
        sete    %cl
        orb     %cl, %dl
        jne     .L4
        cmpq    $a, %rax
        jne     .L6
.L4:
        call    k.isra.0
        andl    $5, a(%rip)
        xorl    %eax, %eax
        addq    $8, %rsp
        ret
.L6:
        movl    $.LC0, %esi
        movl    $__PRETTY_FUNCTION__.0, %ecx
        movl    $4, %edx
        movq    %rsi, %rdi
        call    __assert_fail

Bisects to r14-2674-gd0de3bf9175

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
   Target Milestone|---                         |14.0

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-08-03
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.
The first major IR difference between GCC 13 and trunk happens in DOM2 where 13
would thread some jumps:
_10  : [irange] int [0, 5] NONZERO 0x5
  Threaded jump 6 --> 7 to 10
  Threaded jump 5 --> 7 to 10

While the trunk does not.

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I didn't anticipate the trick triggering with FRE but we have

Value numbering stmt = _6 = _5 | 64;
Setting value number of _6 to _6 (changed)
...
Value numbering stmt = _9 = _8 & 5;
Setting value number of _9 to _9 (changed)
...
Replaced a with _6 in all uses of _8 = a;
Applying pattern match.pd:184, gimple-match-10.cc:6142
Applying pattern match.pd:1962, gimple-match-6.cc:16850
gimple_simplified to _10 = _5 & 5;
_9 = _10;

that's the old issue that when we are recursively simplifying pattern
results like

  (bit_ior (bit_and @0 @2) (bit_and! @1 @2)))

we need to push operands, but when any outer operation simplifies
away we can't (or rather do not) pop them again (also when asked
to never push we'd fail the pattern before trying to simplify
the outer operation).  That can then result in such stray copies
to appear.

So the first IL difference is

--- a/t.c.114t.fre3     2023-08-04 09:22:55.380428835 +0200
+++ b/t.c.114t.fre3     2023-08-04 09:21:50.455470894 +0200
@@ -159,7 +159,7 @@
   a = _6;
   _10 = _5 & 5;
   _9 = _10;
-  a = _9;
+  a = _10;
   return 0;

 }

but that vanishes in copyprop1.  ifcombine then gets different SSA names
assigned which means different association of bitwise or operations.  For
some reason this causes the divergence in DOM2.

After copyprop2 we have

-FREE_SSANAMES: 12, 21, 3, 4, 7, 16, 15, 19, 22, 26, 17, 27, 13, 6, 20, 25, 8,
18, 24, 9, 
+FREE_SSANAMES: 12, 21, 3, 4, 7, 16, 15, 19, 22, 26, 17, 27, 9, 13, 6, 20, 25,
8, 18, 24, 

so the same SSA names are in the freelist but as that is unordered we pick
different names when re-using.

In the DOM2 pass you can see that ranger behaves slightly different when
processing operands in different order for commutative operations like
bitwise or in this case, that leads to the observed difference in threading.

Tracing ranger reveals too many differences, in the end I'd say "bad luck",
but maybe ranger folks want to investigate as well?

I'm not convinced we need to sort FREE_SSANAMES, solving the slightly
imperfect simplification for match would be nice.

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
One thing I noticed (I don't know if causes the missed optimization) is that we
have before PRE:
```
  <bb 4> [local count: 1073531371]:
  if (a.0_1 != 0)
    goto <bb 6>; [50.00%]
  else
    goto <bb 5>; [50.00%]

  <bb 5> [local count: 536765686]:
  if (_28 == &d)
    goto <bb 9>; [30.00%]
  else
    goto <bb 7>; [70.00%]

  <bb 6> [local count: 536765685]:
  if (_28 == &d)
    goto <bb 9>; [30.00%]
  else
    goto <bb 7>; [70.00%]
```
Which obvious should just be `if (_28 == &d) goto bb9; else goto bb7;` and not
check `a.0_1` at all.

I tried a reduced testcase but PRE optimizes it:
```
int g();
int h();

int j, l;

int f(int a, int *b)
{
        if (a == 0)
        {
                if (b == &j) goto L9; else goto L7;
        }
        else
        {
                if (b == &j) goto L9; else goto L7;
        }
L7: return g();
L9: return h();
}
```

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> One thing I noticed (I don't know if causes the missed optimization) is that
> we have before PRE:
> ```
>   <bb 4> [local count: 1073531371]:
>   if (a.0_1 != 0)
>     goto <bb 6>; [50.00%]
>   else
>     goto <bb 5>; [50.00%]
> 
>   <bb 5> [local count: 536765686]:
>   if (_28 == &d)
>     goto <bb 9>; [30.00%]
>   else
>     goto <bb 7>; [70.00%]
> 
>   <bb 6> [local count: 536765685]:
>   if (_28 == &d)
>     goto <bb 9>; [30.00%]
>   else
>     goto <bb 7>; [70.00%]
> ```
> Which obvious should just be `if (_28 == &d) goto bb9; else goto bb7;` and
> not check `a.0_1` at all.

I wonder if ifcombine could optimize that instead of requiring PRE. I think
that might even fix the issue too.

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a patch for what I laid out in comment #3 and it solves the original
issue too because after ifcombine we have:
  _24 = _28 == &c;
  _18 = _28 == &d;
  _8 = _18 | _24;
  _25 = _28 == &a;
  _20 = _8 | _25;
  if (_20 != 0)
    goto <bb 4>; [99.98%]
  else
    goto <bb 3>; [0.02%]

  <bb 3> [local count: 210453]:
  __assert_fail ("", "", 4, &__PRETTY_FUNCTION__);

  <bb 4> [local count: 536765685]:
  _6 = _28 == &c;
  _13 = _28 == &d;
  _9 = _6 | _13;
  _27 = _28 == &a;
  _17 = _9 | _27;
  if (_17 != 0)
    goto <bb 6>; [99.98%]
  else
    goto <bb 5>; [0.02%]

Which then obviously gets optimized by DOM2.

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |patch

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch posted:
https://gcc.gnu.org/pipermail/gcc-patches/2023-August/628525.html

It can be improved to do also compare swapping, but that is recorded as PR
111167 .

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[rguenther at suse dot de]

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

--- Comment #7 from rguenther at suse dot de <rguenther at suse dot de> ---
On Sat, 26 Aug 2023, pinskia at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110891
> 
> --- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> (In reply to Andrew Pinski from comment #3)
> > One thing I noticed (I don't know if causes the missed optimization) is that
> > we have before PRE:
> > ```
> >   <bb 4> [local count: 1073531371]:
> >   if (a.0_1 != 0)
> >     goto <bb 6>; [50.00%]
> >   else
> >     goto <bb 5>; [50.00%]
> > 
> >   <bb 5> [local count: 536765686]:
> >   if (_28 == &d)
> >     goto <bb 9>; [30.00%]
> >   else
> >     goto <bb 7>; [70.00%]
> > 
> >   <bb 6> [local count: 536765685]:
> >   if (_28 == &d)
> >     goto <bb 9>; [30.00%]
> >   else
> >     goto <bb 7>; [70.00%]
> > ```
> > Which obvious should just be `if (_28 == &d) goto bb9; else goto bb7;` and
> > not check `a.0_1` at all.
> 
> I wonder if ifcombine could optimize that instead of requiring PRE. I think
> that might even fix the issue too.

Note it's the tail-merging code that optimizes this, not PRE (yeah,
those passes should be ripped apart)

[Bug tree-optimization/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[law at gcc dot gnu.org]

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

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/110891] [14 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[law at gcc dot gnu.org]

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

--- Comment #8 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Note that Richi was supportive of the patch and just asked for a few minor
changes.  Pinski, if you wanted to take care of Richi's comments we could get
this one off the P2 list.

[Bug tree-optimization/110891] [14/15 Regression] Dead Code Elimination Regression since r14-2674-gd0de3bf9175

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|14.0                        |14.2

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