[Bug tree-optimization/102983] New: [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[Bug tree-optimization/102983] New: [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[theodort at inf dot ethz.ch]

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

            Bug ID: 102983
           Summary: [12 Regression] Dead Code Elimination Regression at
                    -O3 (trunk vs 11.2.0)
           Product: gcc
           Version: 12.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 test.c
void foo(void);

static int a = 1;

int main() {
  int c = 0;
  for (int b = 0; b <= 0; b++) {
    if (!a)
      foo();
    if (b > c){
      if (c)
        continue;
      a = 0;
    }
    c = 1;
  }
}

11.2.0 at -O3 can eliminate the call to foo but trunk at -O3 cannot:

gcc-11 test.c -O3 -S -o /dev/stdout
...
main:
.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        ret
        .cfi_endproc


gcc-trunk test.c -O3 -S -o /dev/stdout
...
main:
.LFB0:
        .cfi_startproc
        movl    a(%rip), %ecx
        testl   %ecx, %ecx
        je      .L8
        xorl    %eax, %eax
        ret
.L8:
        pushq   %rax
        .cfi_def_cfa_offset 16
        call    foo
        xorl    %eax, %eax
        popq    %rdx
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc


gcc-trunk  -v
Using built-in specs.
Target: x86_64-pc-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.0.0 20211028 (experimental) (GCC)


Started with
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=398572c1544d8b7541862401b985ae7e855cb8fb

[Bug tree-optimization/102983] [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2021-10-28
     Ever confirmed|0                           |1
   Target Milestone|---                         |12.0

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm:
  <bb 5> :
  if (c_3 < 0)
    goto <bb 6>; [INV]
  else
    goto <bb 9>; [INV]

  <bb 6> :
  if (c_3 != 0)
    goto <bb 7>; [INV]
  else
    goto <bb 8>; [INV]


=========== BB 5 ============
Imports: c_3  b_4  
Exports: c_3  b_4  
c_3     int [-INF, 1]
b_4     int [0, 0]
    <bb 5> :
    if (c_3 < 0)
      goto <bb 6>; [INV]
    else
      goto <bb 9>; [INV]

5->6  (T) c_3 :         int [-INF, -1]
5->6  (T) b_4 :         int [0, 0]
5->9  (F) c_3 :         int [0, 1]
5->9  (F) b_4 :         int [0, 0]

=========== BB 6 ============
Imports: c_3  
Exports: c_3  
c_3     int [-INF, 0]
b_4     int [0, 0]
    <bb 6> :
    if (c_3 != 0)
      goto <bb 7>; [INV]
    else
      goto <bb 8>; [INV]

6->7  (T) c_3 :         int [-INF, -1]
6->8  (F) c_3 :         int [0, 0]


Hmmmm.

[Bug tree-optimization/102983] [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug tree-optimization/102983] [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
This is a bit more interesting.
The IL starts the pass as

 <bb 5> :
  if (c_3 < b_4)
    goto <bb 6>; [INV]
  else
    goto <bb 9>; [INV]

  <bb 6> :
  if (c_3 != 0)
    goto <bb 7>; [INV]
  else
    goto <bb 8>; [INV]

<...>
  <bb 11> :
  # c_3 = PHI <0(2), c_2(10)>
  # b_4 = PHI <0(2), b_16(10)>
  if (b_4 <= 0)
    goto <bb 3>; [INV]
  else
    goto <bb 12>; [INV]

so the initial condition is "if (c_3 < b_4)"
the initial attempt to calculate c_3 = PHI flows along and uses a value of b_4
determined by loop analysis of [0,1].  (we haven't gotten to propagating b_4
along the back edges yet)  so it ends up deciding c_3 has a range of [-INF, 1]
We then plod along, and eventually handle b_4, and propagate that b_4 is [0,0[
on the edge 11->3.

There is no direct dependency between c_3 and b_4, so there are no values going
stale due to this updated value.

Meanwhile, we eventually visit the if (c_3 < b_4) stmt, and b_4 is known to be
0, so the simplifier changes this to if (c_3 < 0). 

Ranger however, doesnt know this was simplified, and at the moment doesn't
think it needs to recalculate any outgoing ranges and update on-entry cache
values in successor blocks. It dDoesn't realize there is a reason to
recalculate it.

Whenever we successfully fold or simplify a conditional, we probably need to
check if any values should then be propagated.  I believe that it will happen
automatically for anything that is defined by the statement due to the nature
of the temporal cache.  Statements like GIMPLE_COND which have no LHS have no
triggers.

[Bug tree-optimization/102983] [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

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

commit r12-4788-gcb596fd43667f92c4cb037a4ee8b2061c393ba60
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Oct 28 13:31:17 2021 -0400

    Perform on-entry propagation after range_of_stmt on a gcond.

    Propagation is automatically done by the temporal cache when defs are
    out of date from the names on the RHS, but a gcond has no LHS, and any
    updates on the RHS are never propagated.  Always propagate them.

            gcc/
            PR tree-optimization/102983
            * gimple-range-cache.h (propagate_updated_value): Make public.
            * gimple-range.cc (gimple_ranger::range_of_stmt): Propagate exports
            when processing gcond stmts.

            gcc/testsuite/
            * gcc.dg/pr102983.c: New.

[Bug tree-optimization/102983] [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
Rather than trying to fix this after the fact in the VRP folder when something
is simplified,  I fixed it directly inside ranger when it is processing gcond
statements.  
Ranger will now update the cache following any range_of_stmt calls on a gcond
so we will always be up to date.  This way non-vrp clients will also get the
same updates.