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

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.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