[Bug tree-optimization/103514] New: Missing XOR-EQ-AND Optimization

[Bug tree-optimization/103514] New: Missing XOR-EQ-AND Optimization

[navidrahimi at microsoft dot com]

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

            Bug ID: 103514
           Summary: Missing XOR-EQ-AND Optimization
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: navidrahimi at microsoft dot com
  Target Milestone: ---

We are not optimizing &&-^-== combination, LLVM does it [1]:

// Proof of correctness https://alive2.llvm.org/ce/z/a4tuWF
bool
src (bool a, bool b)
{
    return (a && b) == (a ^ b);
}

bool
tgt (bool a, bool b)
{
    return !(a || b);
}


// Proof of correctness https://alive2.llvm.org/ce/z/w-iotd
bool
src (bool a, bool b)
{
     return (a && b) ^ (a == b);
}

bool
tgt (bool a, bool b)
{
    return !(a || b);
}


I will be sending a patch for this. This will solve it, I have to run the
testsuite and write a few tests:

/* (a && b) first_op (a second_op b) -> !(a || b) */
(for first_op (bit_xor eq)
 (for second_op (bit_xor eq)
 (simplify 
  (first_op:c (bit_and:c truth_valued_p@0 truth_valued_p@1) (second_op:c @0
@1))
   (if (first_op != second_op)
    (bit_not (bit_ior @0 @1))))))



1) https://compiler-explorer.com/z/WqTxYhG3s

[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note the loop should be:
(for first_op  (bit_xor eq     )
     second_op (eq      bit_xor)
 (simplify 
  (first_op:c (bit_and:c truth_valued_p@0 truth_valued_p@1) (second_op:c @0
@1))
   (bit_not (bit_ior @0 @1)))))


No reason fore the double for loop

[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization

[navidrahimi at microsoft dot com]

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

--- Comment #2 from Navid Rahimi <navidrahimi at microsoft dot com> ---
Exactly. Actually in my final version I had it with single loop, but didn't
know I can remove the condition too. Thanks Andrew.

[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |12.0
     Ever confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2021-12-01
             Status|UNCONFIRMED                 |NEW

[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r12-6928-gcb3ac1985a5332fa811a62844adb33ca140bd4ba
Author: Navid Rahimi <navidrahimi@microsoft.com>
Date:   Fri Jan 28 17:11:30 2022 -0500

    tree-optimization/103514 Missing XOR-EQ-AND Optimization

    This patch will add the missed pattern described in bug 103514 [1] to the
match.pd. [1] includes proof of correctness for the patch too.

    1) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514

    gcc/
            PR tree-optimization/103514
            * match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.
            (a & b) == (a ^ b) -> !(a | b): New optimization.

    gcc/testsuite
            * gcc.dg/tree-ssa/pr103514.c: Testcase for this optimization.

[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization

[navidr at gcc dot gnu.org]

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

Navid Rahimi <navidr at gcc dot gnu.org> changed:

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

--- Comment #4 from Navid Rahimi <navidr at gcc dot gnu.org> ---
Thanks Jeff.

[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:263a5944fc806396ecc3eff3d96277602e88ae2b

commit r12-6942-g263a5944fc806396ecc3eff3d96277602e88ae2b
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Jan 31 10:30:58 2022 +0100

    testsuite: Fix up tree-ssa/pr103514.c testcase [PR103514]

    > > PR tree-optimization/103514
    > >     * match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.
    > >     * match.pd (a & b) == (a ^ b) -> !(a | b): New optimization.
    > >     * gcc.dg/tree-ssa/pr103514.c: Testcase for this optimization.
    > >
    > > 1) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514
    > Note the bug was filed an fixed during stage3, review just didn't happen
in
    > a reasonable timeframe.
    >
    > I'm going to ACK this for the trunk and go ahead and commit it for you.

    The testcase FAILs on short-circuit targets like powerpc64le-linux.
    While the first 2 functions are identical, the last two look like:
      <bb 2> :
      if (a_5(D) != 0)
        goto <bb 3>; [INV]
      else
        goto <bb 4>; [INV]

      <bb 3> :
      if (b_6(D) != 0)
        goto <bb 5>; [INV]
      else
        goto <bb 4>; [INV]

      <bb 4> :

      <bb 5> :
      # iftmp.1_4 = PHI <1(3), 0(4)>
      _1 = a_5(D) == b_6(D);
      _2 = (int) _1;
      _3 = _2 ^ iftmp.1_4;
      _9 = _2 != iftmp.1_4;
      return _9;
    instead of the expected:
      <bb 2> :
      _3 = a_8(D) & b_9(D);
      _4 = (int) _3;
      _5 = a_8(D) == b_9(D);
      _6 = (int) _5;
      _1 = a_8(D) | b_9(D);
      _2 = ~_1;
      _7 = (int) _2;
      _10 = ~_1;
      return _10;
    so no wonder it doesn't match.  E.g. x86_64-linux will also use jumps
    if it isn't just a && b but a && b && c && d (will do
    a & b and c & d tests and jump based on those.

    As it is too late to implement this optimization even for the short
    circuiting targets this late (not even sure which pass would be best),
    this patch just forces non-short-circuiting for the test.

    2022-01-31  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/103514
            * gcc.dg/tree-ssa/pr103514.c: Add
            --param logical-op-non-short-circuit=1 to dg-options.