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

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

[yann at ywg dot ch]

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

            Bug ID: 105086
           Summary: Dead Code Elimination Regression at -Os (trunk vs.
                    11.2.0) 25
           Product: gcc
           Version: 12.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 52702
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52702&action=edit
The case presented.

cat case.c #25
void foo();
int main() {
  unsigned a = -23;
  for (; a >= 2; ++a)
    if (a == 55)
      foo();
}

`gcc-0127fb1b78a36a7b228d4b3fe32eedfc8d273363 (trunk) -Os` can not eliminate
`foo` but `gcc-releases/gcc-11.2.0 -Os` can.

`gcc-0127fb1b78a36a7b228d4b3fe32eedfc8d273363 (trunk) -Os -S -o /dev/stdout
case.c`
--------- OUTPUT ---------
main:
.LFB0:
        .cfi_startproc
        movl    $-23, %eax
.L6:
        cmpl    $55, %eax
        je      .L10
        incl    %eax
        jne     .L6
        xorl    %eax, %eax
        ret
.L10:
        pushq   %rax
        .cfi_def_cfa_offset 16
.L7:
        xorl    %eax, %eax
        call    foo
        movl    $56, %eax
.L2:
        incl    %eax
        je      .L12
        cmpl    $55, %eax
        jne     .L2
        jmp     .L7
.L12:
        xorl    %eax, %eax
        popq    %rdx
        .cfi_def_cfa_offset 8
        ret
---------- END OUTPUT ---------


`gcc-releases/gcc-11.2.0 -Os -S -o /dev/stdout case.c`
--------- OUTPUT ---------
main:
.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        ret
---------- END OUTPUT ---------


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

----- Build information -----
----- 0127fb1b78a36a7b228d4b3fe32eedfc8d273363 (trunk)
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++
--prefix=/zdata/compiler_cache/gcc-0127fb1b78a36a7b228d4b3fe32eedfc8d273363
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.0.1 20220328 (experimental) (GCC)

----- releases/gcc-11.2.0
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++
--prefix=/zdata/compiler_cache/gcc-01a9836c07053b3286b2259d6b628c7583413f55
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.2.0 (GCC)

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
                 CC|                            |amacleod at redhat dot com,
                   |                            |jakub at gcc dot gnu.org
   Target Milestone|---                         |12.0
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-03-28
            Summary|Dead Code Elimination       |[12 Regression] Dead Code
                   |Regression at -Os (trunk    |Elimination Regression at
                   |vs. 11.2.0) 25              |-Os (trunk vs. 11.2.0) 25

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r12-4871-g502ffb1f389011b28ee51815242c7397790802d5

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
Ranger VRP doesn't simulate edges the same way VRP does. It looks like VRP
simulates the back edge twice and the second time notes that the MAX value is
greater than it was before and "projects" the max to +INF to avoid further
simulations and thus executing every instance of the loop. 

This allows it to refine the range in the loop better, which ranger VRP isn't
doing as it is still doing a DOM walk and doesn't revisit the node. ANd I
haven't added any sort of similar "projection" logic to the back edge
processing.

I have an alternate question.  it looks like when we utilize scev to pick up
ranges we just give up if scev_probably_wraps_p() is true.

Analyzing # of iterations of loop 1
  exit condition 1 < [4294967273, + , 1]
  bounds on difference of bases: 4294967272 ... 4294967272
  result:
    # of iterations 23, bounded by 23

Statement (exit)if (a_1 > 1)
is executed at most 23 (bounded by 23) + 1 times in loop 1.

but we neglect to create range for the PHI. We should be able to properly
create a  range for this from the SCEV info rather than giving up?  It would be
[0,0][4294967273, 4294967295]. 

And even with the old value_range we could use anti-range and produce
~[1, 4294967272]?

Is there a practical reason we don't look any closer at wrap cases to see if
they are "simple wraps" or not?  I think that would also solve this issue.

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #2)
> Ranger VRP doesn't simulate edges the same way VRP does. It looks like VRP
> simulates the back edge twice and the second time notes that the MAX value
> is greater than it was before and "projects" the max to +INF to avoid
> further simulations and thus executing every instance of the loop. 

VRP uses optimistic SSA propagation with iteration, to avoid compile-time
explosion we do not simulate IV ranges growing [0,0] -> [0, 1] ->...-> [0, n]
but instead do the cited projection and rely on SCEV to improve the
resulting range.

> This allows it to refine the range in the loop better, which ranger VRP
> isn't doing as it is still doing a DOM walk and doesn't revisit the node.
> ANd I haven't added any sort of similar "projection" logic to the back edge
> processing.

I think ranger simply doesn't simulate SCCs (but I think that's OK)

> I have an alternate question.  it looks like when we utilize scev to pick up
> ranges we just give up if scev_probably_wraps_p() is true.
> 
> Analyzing # of iterations of loop 1
>   exit condition 1 < [4294967273, + , 1]
>   bounds on difference of bases: 4294967272 ... 4294967272
>   result:
>     # of iterations 23, bounded by 23
> 
> Statement (exit)if (a_1 > 1)
> is executed at most 23 (bounded by 23) + 1 times in loop 1.
> 
> but we neglect to create range for the PHI. We should be able to properly
> create a  range for this from the SCEV info rather than giving up?  It would
> be [0,0][4294967273, 4294967295]. 

Well, we give up if the IV wraps because then the logic we have to compute
the IV range doesn't work.  I'm talking about bounds_of_var_in_loop
which basically computes the range as [base, base + step * niter] with
adjustments to create proper ranges for negative step.

> And even with the old value_range we could use anti-range and produce
> ~[1, 4294967272]?

It should use the range as computed by the "iteration", just not use
SCEV to refine it.

> Is there a practical reason we don't look any closer at wrap cases to see if
> they are "simple wraps" or not?  I think that would also solve this issue.

The only reason is that nobody implemented it.  The important thing is to
compute that it will wrap exactly once of course.

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[amacleod at redhat dot com]

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

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Richard Biener from comment #3)
> (In reply to Andrew Macleod from comment #2)

> 
> > I have an alternate question.  it looks like when we utilize scev to pick up
> > ranges we just give up if scev_probably_wraps_p() is true.
> > 
> > Analyzing # of iterations of loop 1
> >   exit condition 1 < [4294967273, + , 1]
> >   bounds on difference of bases: 4294967272 ... 4294967272
> >   result:
> >     # of iterations 23, bounded by 23
> > 
> > Statement (exit)if (a_1 > 1)
> > is executed at most 23 (bounded by 23) + 1 times in loop 1.
> > 
> > but we neglect to create range for the PHI. We should be able to properly
> > create a  range for this from the SCEV info rather than giving up?  It would
> > be [0,0][4294967273, 4294967295]. 
> 
> Well, we give up if the IV wraps because then the logic we have to compute
> the IV range doesn't work.  I'm talking about bounds_of_var_in_loop
> which basically computes the range as [base, base + step * niter] with
> adjustments to create proper ranges for negative step.
> 
Yeah, that is exactly where I was looking, and it looked like it was just to
keep things simple.

> > And even with the old value_range we could use anti-range and produce
> > ~[1, 4294967272]?
> 
> It should use the range as computed by the "iteration", just not use
> SCEV to refine it.
> 
> > Is there a practical reason we don't look any closer at wrap cases to see if
> > they are "simple wraps" or not?  I think that would also solve this issue.
> 
> The only reason is that nobody implemented it.  The important thing is to
> compute that it will wrap exactly once of course.

I suspected as much. I think we can enhance this next stage 1.

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Even wrapping multiple times as long as it wraps finite number of times should
be  possible to handle, no?
for (unsigned int i = ~0U; i != 2; i -= 7)
  ...;
wraps 5 times and has 3681400539 iterations.

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[amacleod at redhat dot com]

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

--- Comment #6 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #5)
> Even wrapping multiple times as long as it wraps finite number of times
> should be  possible to handle, no?
> for (unsigned int i = ~0U; i != 2; i -= 7)
>   ...;
> wraps 5 times and has 3681400539 iterations.

I think if we wrap more than once, we're probably looking at varying anyway :-)

but yes, in theory we could be as precise as we want to be.

[Bug tree-optimization/105086] [12 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P1                          |P2

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Downgrading - lets defer to GCC 13 and consider backporting after GCC 12 is
released.

[Bug tree-optimization/105086] [12/13 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.0                        |12.2

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 12.1 is being released, retargeting bugs to GCC 12.2.

[Bug tree-optimization/105086] [12/13/14 Regression] Dead Code Elimination Regression at -Os (trunk vs. 11.2.0) 25

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.3                        |12.4

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 12.3 is being released, retargeting bugs to GCC 12.4.