[Bug tree-optimization/100864] New: (a&!b) | b is not opimized to a | b for conditionals

[Bug tree-optimization/100864] New: (a&!b) | b is not opimized to a | b for conditionals

[pinskia at gcc dot gnu.org]

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

            Bug ID: 100864
           Summary: (a&!b) | b is not opimized to a | b for conditionals
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pinskia at gcc dot gnu.org
  Target Milestone: ---

Take:
_Bool f(int a, int b, _Bool e)
{
  _Bool c = (a > b);
  _Bool d = !c;
  return (e & d) | c;
}
--- CUT ----
We get currently:
  c_5 = a_3(D) > b_4(D);
  _2 = a_3(D) <= b_4(D);
  _1 = _2 & e_7(D);
  _6 = _1 | c_5;

But this should be optimized to just:

c_5 = a_3(D) <= b_4(D);
_6 = e_7(D) | c_5;

I noticed this while fixing PR 96923.

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
   Last reconfirmed|                            |2021-06-02
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
            Summary|(a&!b) | b is not opimized  |(a&!b) | b is not opimized
                   |to a | b for conditionals   |to a | b for comparisons

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The pattern which matches this when this is not a comparison:
(for bitop (bit_and bit_ior)
     rbitop (bit_ior bit_and)
  /* (x | y) & x -> x */
  /* (x & y) | x -> x */
 (simplify
  (bitop:c (rbitop:c @0 @1) @0)
  @0)
 /* (~x | y) & x -> x & y */
 /* (~x & y) | x -> x | y */
 (simplify
  (bitop:c (rbitop:c (bit_not @0) @1) @0)
  (bitop @0 @1)))

We should be able to add something similar for 
tcc_comparison/inverted_tcc_comparison_with_nans too.

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a patch,
(for bitop (bit_and bit_ior)
     rbitop (bit_ior bit_and)
....
 /* Similar but for comparisons which have been inverted already,
    Note it is hard to similulate inverted tcc_comparison due to NaNs
    so a double for loop is needed and then compare the inverse code
    with the result of invert_tree_comparison is needed.  */
 (for cmp (tcc_comparison)
  (for icmp (tcc_comparison)
   (simplify
    (bitop:c (rbitop:c (icmp @0 @1) @2) (cmp@3 @0 @1))
     (with { enum tree_code ic = invert_tree_comparison
             (cmp, HONOR_NANS (@0)); }
      (if (ic == icmp)
       (bitop @3 @2)))))))

It is more complex than I had liked but it does solve the issue. There is no
way really of simplifying the pattern either, just because of the way match.pd
works :(

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
You can possibly merge it with the

(for bitop (bit_and bit_ior)
     rbitop (bit_ior bit_and)
  /* (x | y) & x -> x */
  /* (x & y) | x -> x */
 (simplify
  (bitop:c (rbitop:c @0 @1) @0)
  @0)
 /* (~x | y) & x -> x & y */
 /* (~x & y) | x -> x | y */
 (simplify
  (bitop:c (rbitop:c (bit_not @0) @1) @0)
  (bitop @0 @1)))

by using sth like logical_inverted_value (you want bit_inverted_value),

Also you don't need

 (for cmp (tcc_comparison)
  (for icmp (tcc_comparison)

but just

  (for cmp (tcc_comparison)
       icmp (inverted_tcc_comparison)
       ncmp (inverted_tcc_comparison_with_nans))
    ...
   (if (ic == icmp || ic == ncmp)
...

right?

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> You can possibly merge it with the
That is where I put it already, the ... was actually that part. Obviously this
was not a patch just showing what was done.

> 
> by using sth like logical_inverted_value (you want bit_inverted_value),
> 
> Also you don't need
> 
>  (for cmp (tcc_comparison)
>   (for icmp (tcc_comparison)
> 
> but just
> 
>   (for cmp (tcc_comparison)
>        icmp (inverted_tcc_comparison)
>        ncmp (inverted_tcc_comparison_with_nans))
>     ...
>    (if (ic == icmp || ic == ncmp)
> ...
> 
> right?

Does not work as there would be many of the same patterns with the above for
loop as inverted_tcc_comparison and inverted_tcc_comparison_with_nans have a
non empty intersection. The reason why it worked for the other usage of
inverted_tcc_comparison/inverted_tcc_comparison_with_nans is because it was the
resulting pattern rather than the matching pattern.

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So what is done for A && !B (and A || !B), is the following:
/* Simple range test simplifications.  */
/* A < B || A >= B -> true.  */
(for test1 (lt le le le ne ge)
     test2 (ge gt ge ne eq ne)
 (simplify
  (bit_ior:c (test1 @0 @1) (test2 @0 @1))
  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
       || VECTOR_INTEGER_TYPE_P (TREE_TYPE (@0)))
   { constant_boolean_node (true, type); })))
/* A < B && A >= B -> false.  */
(for test1 (lt lt lt le ne eq)
     test2 (ge gt eq gt eq gt)
 (simplify
  (bit_and:c (test1 @0 @1) (test2 @0 @1))
  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
       || VECTOR_INTEGER_TYPE_P (TREE_TYPE (@0)))
   { constant_boolean_node (false, type); })))

But this could be expanded to other non-integer types.
For float types e.g (with -ffast-math):
int f(float a, float b)
{
  int c = a == b;
  int d = a != b;
  return c & d;
}
Is not optimized until reassoc1.  I will change that to be similar what I Have
too.

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The a & !b issue is recorded as PR 106164.

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2023-July/62
                   |                            |5289.html
           Keywords|                            |patch

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch submitted:
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/625289.html

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|https://gcc.gnu.org/piperma |https://gcc.gnu.org/piperma
                   |il/gcc-patches/2023-July/62 |il/gcc-patches/2023-July/62
                   |5289.html                   |5792.html

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
New patch:
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/625792.html

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

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

commit r14-2885-gb9237226fdc9387bccf584a811b30c5d3689ffd2
Author: Andrew Pinski <apinski@marvell.com>
Date:   Fri Jul 28 20:27:03 2023 -0700

    tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for
comparisons

    This is a new version of the patch.
    Instead of doing the matching of inversion comparison directly inside
    match, creating a new function (bitwise_inverted_equal_p) to do it.
    It is very similar to bitwise_equal_p that was added in
r14-2751-g2a3556376c69a1fb
    but instead it says `expr1 == ~expr2`. A follow on patch, will
    use this function in other patterns where we try to match `@0` and
`(bit_not @0)`.

    Changed the name bitwise_not_equal_p to bitwise_inverted_equal_p.

    Committed as approved after a Bootstrapped and test on x86_64-linux-gnu
with no regressions.

            PR tree-optimization/100864

    gcc/ChangeLog:

            * generic-match-head.cc (bitwise_inverted_equal_p): New function.
            * gimple-match-head.cc (bitwise_inverted_equal_p): New macro.
            (gimple_bitwise_inverted_equal_p): New function.
            * match.pd ((~x | y) & x): Use bitwise_inverted_equal_p
            instead of direct matching bit_not.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/bitops-3.c: New test.

[Bug tree-optimization/100864] (a&!b) | b is not opimized to a | b for comparisons

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |14.0
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

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