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

[Bug tree-optimization/102705] 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=102705

            Bug ID: 102705
           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 b;
static char c;
static short a(short d, short e) { return e == 0 || d && e == 1 ? 0 : d % e; }
int main() {
  b = c = b >= 2 ? 0 : 1 >> b;
  short f = a(0 >= 0 ^ c, 5);
  if (f == c)
    foo();
  a(0, 9);
}

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

gcc-11.2.0 test.c -S -O3 -o /dev/stdout
main:
.LFB1:
        .cfi_startproc
        movl    b(%rip), %ecx
        movl    $1, %eax
        sarl    %cl, %eax
        movl    %eax, %edx
        xorl    %eax, %eax
        cmpl    $2, %ecx
        cmovl   %edx, %eax
        movsbl  %al, %eax
        movl    %eax, b(%rip)
        xorl    %eax, %eax
        ret
        .cfi_endproc


gcc-trunk test.c -S -O3 -o /dev/stdout
main:
.LFB1:
        .cfi_startproc
        movl    b(%rip), %ecx
        cmpl    $1, %ecx
        jle     .L2
        xorl    %ecx, %ecx
        movl    %ecx, b(%rip)
.L5:
        xorl    %eax, %eax
        ret
.L2:
        movl    $1, %eax
        sarl    %cl, %eax
        movl    %eax, %edx
        movl    %eax, b(%rip)
        xorl    $1, %edx
        movsbw  %dl, %dx
        cmpw    %ax, %dx
        jne     .L5
        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 20211012 (experimental) (GCC)

It started with
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=145bc41dae7c7bfa093d61e77346f98e6a595a0e

[Bug tree-optimization/102705] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-10-12
            Summary|[12 Regression] Dead Code   |[12 Regression] Dead Code
                   |Elimination Regression at   |Elimination Regression at
                   |-O3 (trunk vs 11.2.0)       |-O3 since
                   |                            |r12-2637-g145bc41dae7c7bfa0
                   |                            |93d61e77346f98e6a595a0e
             Status|UNCONFIRMED                 |NEW

[Bug tree-optimization/102705] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[rguenth at gcc dot gnu.org]

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

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

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

[Bug tree-optimization/102705] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[amacleod at redhat dot com]

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

--- Comment #1 from Andrew Macleod <amacleod at redhat dot com> ---
That impact of that patch on this PR is that it teaches range extraction that
[0,1] % [5,5]  is [0,1], unlike before which came up with [0,4]

This in turn causes the thread1 pass to decide to thread something it didn't
thread before.

In the absence of thread1 making this decision (ie, before the patch), the next
pass is VRP/VRpthread which ends up performing the thread anyway, but via
different means, and ever so slightly different IL

By the time we hit DCE3, the differences are very slight:
(We know b.1_1 has a range of [0,1])
Original code where we get the optimization:

  _2 = 1 >> b.1_1;
  iftmp.0_10 = (char) _2;
  _3 = (int) iftmp.0_10;
  b = _3;
  _4 = iftmp.0_10 ^ 1;
  _5 = (int) _4;
  iftmp.6_22 = (short int) _5;
  _6 = (short int) iftmp.0_10;
  if (_6 == iftmp.6_22)
    goto <bb 4>; [49.37%]
  else
    goto <bb 5>; [50.63%]


The next pass is forwprop3, and it reports:
gimple_simplified to iftmp.6_22 = (short int) _4;
gimple_simplified to if (0 != 0)

I think it can see that with  iftmp.0_10 having range [0, 1] that _4,_5 and
iftmp.6_22 are therefore basically ~iftmp.0_10
Thus if can fold the condition as never being true.

And turns this into :

  _2 = 1 >> b.1_1;
  iftmp.0_10 = (char) _2;
  _3 = (int) iftmp.0_10;
  b = _3;
  _4 = iftmp.0_10 ^ 1;
  _5 = (int) _4;
  iftmp.6_22 = (short int) _4;
  _6 = (short int) iftmp.0_10;


Meanwhile, trunk threads earlier, and produces slightly different code .   At
DSE3 time it looks like:

  _2 = 1 >> b.1_1;
  iftmp.0_10 = (char) _2;
  b = _2; 
  _4 = iftmp.0_10 ^ 1;
  _5 = (int) _4;
  iftmp.6_22 = (short int) _5;
  _6 = (short int) _2;
  if (_6 == iftmp.6_22)
    goto <bb 5>; [50.37%]
  else
    goto <bb 6>; [49.63%]

So we have already skipped a few casts as use _2 more directly.

The problem is that the next pass, forwprop3 does not like this new code, and
does not perform the same fold, leaving the condition.   And thus we never lose
the call to foo().

again, _4,_5 and iftmp.6_22 would all be known to be ~iftmp.0_10,  but it looks
like forwprop no longer recognizes that _6 = (short int) _2 makes it 
equivalent to iftmp.0_10 ?

[Bug tree-optimization/102705] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
so it's _10 == _10 ^ 1 vs. (short) _2 == (short)(((char) _2) ^ 1)

likely simplified using logical_inverted_value which works fine for the first
but not the second form.  We're now doing more simplification (looking
through some extra conversions), but that prevents this pattern from matching.

By the time we compute the ranges necessary the conversions are already
pickled too far before simplifying the conditional.

Handling possible variants with patterns is a bit difficult, instead what
looks necessary here is some sort of symbolic equivalence processing that
would include bit ops so it tracks that _6 is _2 and _22 is _2 ^ 1.

What would also help here is simplifying

  # RANGE [0, 1] NONZERO 1
  _2 = 1 >> b.1_1;
  # RANGE [0, 1] NONZERO 1
  iftmp.0_10 = (char) _2;
  # RANGE [0, 1] NONZERO 1
  _4 = iftmp.0_10 ^ 1;
  # RANGE [0, 1] NONZERO 1
  _5 = (int) _4;
  # RANGE [0, 1] NONZERO 1
  iftmp.6_22 = (short int) _5;

via ((char)_2) ^ 1 -> (char)(_2 ^ 1) though we generally do not widen ops.
Which means doing it one level more outer at (int)((char) _2) ^ 1)
-> _2 ^ 1 which is possible because the truncation is a no-op.  That could
be applied to all bit ops when we have range info on the non-constant
operand for the case where the wider type fits in a GPR.

[Bug tree-optimization/102705] [12/13 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[jakub at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/102705] [12/13 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/102705] [12/13/14 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[rguenth at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/102705] [12/13/14 Regression] Dead Code Elimination Regression at -O3 since r12-2637-g145bc41dae7c7bfa093d61e77346f98e6a595a0e

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm:
  iftmp.0_10 = (char) _2;
  _4 = iftmp.0_10 ^ 1;
  _18 = (int) _4;


We have this pattern:
 /* In GIMPLE, getting rid of 2 conversions for one new results
    in smaller IL.  */
 (simplify
  (convert (bitop:cs@2 (nop_convert:s @0) @1))
  (if (GIMPLE
       && TREE_CODE (@1) != INTEGER_CST
       && tree_nop_conversion_p (type, TREE_TYPE (@2))
       && types_match (type, @0)
       && !POINTER_TYPE_P (TREE_TYPE (@0))
       && TREE_CODE (TREE_TYPE (@0)) != OFFSET_TYPE)
   (bitop @0 (convert @1)))))


Except here @1 is CST and the we don't exactly have a nop_conversion, though it
is a "nop" due to the nonzero-bitranges to be less than the inner type.

Maybe we could expand or create a new pattern for this ...