[Bug c/106379] New: DCE depends on order

[Bug c/106379] New: DCE depends on order

[tmayerl at student dot ethz.ch]

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

            Bug ID: 106379
           Summary: DCE depends on order
           Product: gcc
           Version: 12.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tmayerl at student dot ethz.ch
  Target Milestone: ---

In some cases, the compiler's ability to eliminate dead code depends on the
order of the sub-expressions within the if.

GCC detects that the if expression in the following code snippet evaluates to
false and thus removes the dead code:

#include <stdio.h>
#include <stdbool.h>

static void __attribute__ ((noinline)) DCEMarker0_() {printf("DCE2.0");}

void f(bool c, bool s) {
    if (((!c == !s) && !(c) && s)) {
        DCEMarker0_();
    }
}

In the following snippet the expressions are swapped (the semantics stay the
same). However, GCC cannot eliminate the dead code anymore:

#include <stdio.h>
#include <stdbool.h>

static void __attribute__ ((noinline)) DCEMarker0_() {printf("DCE2.0");}

void f(bool c, bool s) {
    if ((!s == !c) && s && !(c)) {
        DCEMarker0_();
    }
}


This can also be seen via the following Compiler Explorer link:
https://godbolt.org/z/vTqhc46qY

[Bug tree-optimization/106379] DCE depends on order

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2022-07-21
                 CC|                            |amacleod at redhat dot com
          Component|c                           |tree-optimization

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  We don't recognize the pattern in GENERIC folding, instead for the
good case VRP1 handles

  _Bool _1;
  _Bool _2;

  <bb 2> [local count: 1073741824]:
  _1 = ~c_4(D);
  if (c_4(D) != s_5(D))
    goto <bb 5>; [66.00%]
  else
    goto <bb 3>; [34.00%]

  <bb 3> [local count: 365072224]:
  _2 = _1 & s_5(D);
  if (_2 != 0)
    goto <bb 4>; [33.00%]
  else
    goto <bb 5>; [67.00%]

  <bb 4> [local count: 120473833]:
  DCEMarker0_ ();

  <bb 5> [local count: 1073741824]:
  return;

well while not handling

  _Bool _1;
  _Bool _2;

  <bb 2> [local count: 1073741824]:
  if (s_4(D) != c_5(D))
    goto <bb 5>; [66.00%]
  else
    goto <bb 3>; [34.00%]

  <bb 3> [local count: 365072224]:
  _1 = ~c_5(D);
  _2 = _1 & s_4(D);
  if (_2 != 0)
    goto <bb 4>; [33.00%]
  else
    goto <bb 5>; [67.00%]

  <bb 4> [local count: 120473833]:
  DCEMarker0_ ();

  <bb 5> [local count: 1073741824]:
  return;

we are probably very early defeating equivalence handling by folding
!a == !b to !a ^ b (and which one gets the inversion depends on the order
which is the underlying issue this PR points out).

It's also apparent that we fail to simplify !a == !b to a == b for boolean
a, b.  We arrive there via fold_binary_loc's

  /* ARG0 is the first operand of EXPR, and ARG1 is the second operand.

     First check for cases where an arithmetic operation is applied to a
     compound, conditional, or comparison operation.  Push the arithmetic
     operation inside the compound or conditional to see if any folding
     can then be done.  Convert comparison to conditional for this purpose.
     The also optimizes non-constant cases that used to be done in
     expand_expr.

     Before we do that, see if this is a BIT_AND_EXPR or a BIT_IOR_EXPR,
     one of the operands is a comparison and the other is a comparison, a
     BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
     code below would make the expression more complex.  Change it to a
     TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
     TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */

which generates !a ^ !b which is eventually inverted to !a ^ b.

Adding

(simplify
 (bit_not (bit_xor truth_valued_p@0 truth_valued_p@1))
 (eq @0 @1))

fixes this but code generation of

_Bool foo (_Bool a, _Bool b)
{
  return !a == !b;
}

changes from

        xorl    %edi, %esi
        movl    %esi, %eax
        xorl    $1, %eax
        ret

to

        cmpb    %sil, %dil
        sete    %al

[Bug tree-optimization/106379] DCE depends on order

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
With that, what remains looks like a VRP/ranger issue though.

Good:

  <bb 2> [local count: 1073741824]:
  _1 = ~c_4(D);
  if (c_4(D) == s_5(D))
    goto <bb 3>; [34.00%]
  else
    goto <bb 5>; [66.00%]

  <bb 3> [local count: 365072224]:
  _2 = _1 & s_5(D);
  if (_2 != 0)
    goto <bb 4>; [33.00%]
  else
    goto <bb 5>; [67.00%]

  <bb 4> [local count: 120473833]:
  DCEMarker0_ ();

  <bb 5> [local count: 1073741824]:

Bad:

  <bb 2> [local count: 1073741824]:
  if (s_4(D) == c_5(D))
    goto <bb 3>; [34.00%]
  else
    goto <bb 5>; [66.00%]

  <bb 3> [local count: 365072224]:
  _1 = ~c_5(D);
  _2 = _1 & s_4(D);
  if (_2 != 0)
    goto <bb 4>; [33.00%]
  else
    goto <bb 5>; [67.00%]

  <bb 4> [local count: 120473833]:
  DCEMarker0_ ();

  <bb 5> [local count: 1073741824]:

the difference is just the point of definition of _1.

[Bug tree-optimization/106379] DCE depends on order

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:375668e0508fbe173af1ed519d8ae2b79f388d94

commit r13-1779-g375668e0508fbe173af1ed519d8ae2b79f388d94
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Jul 21 13:20:47 2022 +0200

    tree-optimization/106379 - add missing ~(a ^ b) folding for _Bool

    The following makes sure to fold ~(a ^ b) to a == b for truth
    values (but not vectors, we'd have to check for vector support of
    equality).  That turns the PR106379 testcase into a ranger one.

    Note that while we arrive at ~(a ^ b) in a convoluted way from
    original !a == !b one can eventually write the expression this
    way directly as well.

            PR tree-optimization/106379
            * match.pd (~(a ^ b) -> a == b): New pattern.

            * gcc.dg/pr106379-1.c: New testcase.

[Bug tree-optimization/106379] DCE depends on order

[amacleod at redhat dot com]

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

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
Ranger actually appears to handle both cases the same.  VRP1 gets it whilst
ranger does not.  I believe this to be because we are match and simplifying 

  _1 = ~c_5(D);
  _2 = _1 & s_4(D);

with c_5 == s_4... but at this point, the simplification code doesn't
understand the relation oracle, so I beleive it to be missing the fact that _2
will evaluate to 0 because it doesnt see the equivalency. VRP1 gets it because
its in intergrated in the legacy range that passed in as an equivset.

I will shortly get to some equivalency processing during simplificatoin as a
part of trying to remove VRP1.  We should then pick this up with in EVRP.

[Bug tree-optimization/106379] DCE depends on order

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         Depends on|                            |106380
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
           Severity|normal                      |enhancement

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---

  _1 = ~c_5(D);
  _2 = _1 & s_4(D);

Mine.
That is `c < s`.  So the same as PR 106380 .


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106380
[Bug 106380] DCE depends on datatype used (bool vs unsigned)

[Bug tree-optimization/106379] DCE depends on order

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=107880

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
>   _1 = ~c_5(D);
>   _2 = _1 & s_4(D);
> 
> Mine.
> That is `c < s`.  So the same as PR 106380 .

Or PR 107880 .

[Bug tree-optimization/106379] DCE depends on order

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |106380, 106505, 106381
         Depends on|106380                      |

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
bug 106380, bug 106381 and bug 106505 are all the basic issue now transforming
`~a & b` and `~a | b` into `a < b` and `a <= b`.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106380
[Bug 106380] DCE depends on datatype used (bool vs unsigned)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106381
[Bug 106381] DCE depends on used programming language (C vs C++)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106505
[Bug 106505] DCE depends on whether if or else is used