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

[Andrew Pinski <pinskia@gmail.com>]

On Wed, Aug 2, 2023 at 10:13 AM Prathamesh Kulkarni via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Mon, 31 Jul 2023 at 22:39, Andrew Pinski via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > 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.
> Hi Andrew,
> Unfortunately, this patch (committed in
> 2bae476b511dc441bf61da8a49cca655575e7dd6) causes
> segmentation fault for pr33133.c on aarch64-linux-gnu because of
> infinite recursion.

A similar issue is recorded as PR 110874 which I am debugging right now.

Thanks,
Andrew

>
> Running the test under gdb shows:
> Program received signal SIGSEGV, Segmentation fault.
> operand_compare::operand_equal_p (this=0x29dc680
> <default_compare_instance>, arg0=0xfffff7789a68, arg1=0xfffff7789f30,
>     flags=16) at ../../gcc/gcc/fold-const.cc:3088
> 3088    {
> (gdb) bt
> #0  operand_compare::operand_equal_p (this=0x29dc680
> <default_compare_instance>, arg0=0xfffff7789a68, arg1=0xfffff7789f30,
>     flags=16) at ../../gcc/gcc/fold-const.cc:3088
> #1  0x0000000000a90394 in operand_compare::verify_hash_value
> (this=this@entry=0x29dc680 <default_compare_instance>,
>     arg0=arg0@entry=0xfffff7789a68, arg1=arg1@entry=0xfffff7789f30,
> flags=flags@entry=0, ret=ret@entry=0xfffffc000157)
>     at ../../gcc/gcc/fold-const.cc:4074
> #2  0x0000000000a9351c in operand_compare::verify_hash_value
> (ret=0xfffffc000157, flags=0, arg1=0xfffff7789f30,
>     arg0=0xfffff7789a68, this=0x29dc680 <default_compare_instance>) at
> ../../gcc/gcc/fold-const.cc:4072
> #3  operand_compare::operand_equal_p (this=this@entry=0x29dc680
> <default_compare_instance>, arg0=arg0@entry=0xfffff7789a68,
>     arg1=arg1@entry=0xfffff7789f30, flags=flags@entry=0) at
> ../../gcc/gcc/fold-const.cc:3090
> #4  0x0000000000a9791c in operand_equal_p
> (arg0=arg0@entry=0xfffff7789a68, arg1=arg1@entry=0xfffff7789f30,
>     flags=flags@entry=0) at ../../gcc/gcc/fold-const.cc:4105
> #5  0x0000000001d38dd0 in gimple_bitwise_inverted_equal_p
> (expr1=0xfffff7789a68, expr2=0xfffff7789f30, valueize=
>     0x112d698 <rpo_vn_valueize(tree_node*)>) at
> ../../gcc/gcc/gimple-match-head.cc:284
> #6  0x0000000001d38e80 in gimple_bitwise_inverted_equal_p
> (expr1=0xfffff7789a68, expr2=0xfffff77d0240,
>     valueize=0x112d698 <rpo_vn_valueize(tree_node*)>) at
> ../../gcc/gcc/gimple-match-head.cc:296
> #7  0x0000000001d38e80 in gimple_bitwise_inverted_equal_p
> (expr1=0xfffff7789a68, expr2=0xfffff7789f30,
>     valueize=0x112d698 <rpo_vn_valueize(tree_node*)>) at
> ../../gcc/gcc/gimple-match-head.cc:296
> #8  0x0000000001d38e80 in gimple_bitwise_inverted_equal_p
> (expr1=0xfffff7789a68, expr2=0xfffff77d0240,
> ...
>
> It seems to recurse cyclically with expr2=0xfffff7789f30 ->
> expr2=0xfffff77d0240 eventually leading to segfault.
> while expr1=0xfffff7789a68 remains same throughout the stack frames.
>
> Thanks,
> Prathamesh
> >
> >         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.
> > ---
> >  gcc/generic-match-head.cc                | 42 ++++++++++++++
> >  gcc/gimple-match-head.cc                 | 71 ++++++++++++++++++++++++
> >  gcc/match.pd                             |  5 +-
> >  gcc/testsuite/gcc.dg/tree-ssa/bitops-3.c | 67 ++++++++++++++++++++++
> >  4 files changed, 183 insertions(+), 2 deletions(-)
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitops-3.c
> >
> > diff --git a/gcc/generic-match-head.cc b/gcc/generic-match-head.cc
> > index a71c0727b0b..ddaf22f2179 100644
> > --- a/gcc/generic-match-head.cc
> > +++ b/gcc/generic-match-head.cc
> > @@ -121,3 +121,45 @@ bitwise_equal_p (tree expr1, tree expr2)
> >      return wi::to_wide (expr1) == wi::to_wide (expr2);
> >    return operand_equal_p (expr1, expr2, 0);
> >  }
> > +
> > +/* Return true if EXPR1 and EXPR2 have the bitwise opposite value,
> > +   but not necessarily same type.
> > +   The types can differ through nop conversions.  */
> > +
> > +static inline bool
> > +bitwise_inverted_equal_p (tree expr1, tree expr2)
> > +{
> > +  STRIP_NOPS (expr1);
> > +  STRIP_NOPS (expr2);
> > +  if (expr1 == expr2)
> > +    return false;
> > +  if (!tree_nop_conversion_p (TREE_TYPE (expr1), TREE_TYPE (expr2)))
> > +    return false;
> > +  if (TREE_CODE (expr1) == INTEGER_CST && TREE_CODE (expr2) == INTEGER_CST)
> > +    return wi::to_wide (expr1) == ~wi::to_wide (expr2);
> > +  if (operand_equal_p (expr1, expr2, 0))
> > +    return false;
> > +  if (TREE_CODE (expr1) == BIT_NOT_EXPR
> > +      && bitwise_equal_p (TREE_OPERAND (expr1, 0), expr2))
> > +    return true;
> > +  if (TREE_CODE (expr2) == BIT_NOT_EXPR
> > +      && bitwise_equal_p (expr1, TREE_OPERAND (expr2, 0)))
> > +    return true;
> > +  if (COMPARISON_CLASS_P (expr1)
> > +      && COMPARISON_CLASS_P (expr2))
> > +    {
> > +      tree op10 = TREE_OPERAND (expr1, 0);
> > +      tree op20 = TREE_OPERAND (expr2, 0);
> > +      if (!operand_equal_p (op10, op20))
> > +       return false;
> > +      tree op11 = TREE_OPERAND (expr1, 1);
> > +      tree op21 = TREE_OPERAND (expr2, 1);
> > +      if (!operand_equal_p (op11, op21))
> > +       return false;
> > +      if (invert_tree_comparison (TREE_CODE (expr1),
> > +                                 HONOR_NANS (op10))
> > +         == TREE_CODE (expr2))
> > +       return true;
> > +    }
> > +  return false;
> > +}
> > diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
> > index 5d6d26d009b..0265e55be93 100644
> > --- a/gcc/gimple-match-head.cc
> > +++ b/gcc/gimple-match-head.cc
> > @@ -263,3 +263,74 @@ gimple_bitwise_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
> >      return true;
> >    return false;
> >  }
> > +
> > +/* Return true if EXPR1 and EXPR2 have the bitwise opposite value,
> > +   but not necessarily same type.
> > +   The types can differ through nop conversions.  */
> > +#define bitwise_inverted_equal_p(expr1, expr2) \
> > +  gimple_bitwise_inverted_equal_p (expr1, expr2, valueize)
> > +
> > +/* Helper function for bitwise_equal_p macro.  */
> > +
> > +static inline bool
> > +gimple_bitwise_inverted_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
> > +{
> > +  if (expr1 == expr2)
> > +    return false;
> > +  if (!tree_nop_conversion_p (TREE_TYPE (expr1), TREE_TYPE (expr2)))
> > +    return false;
> > +  if (TREE_CODE (expr1) == INTEGER_CST && TREE_CODE (expr2) == INTEGER_CST)
> > +    return wi::to_wide (expr1) == ~wi::to_wide (expr2);
> > +  if (operand_equal_p (expr1, expr2, 0))
> > +    return false;
> > +
> > +  tree other;
> > +  if (gimple_nop_convert (expr1, &other, valueize)
> > +      && gimple_bitwise_inverted_equal_p (other, expr2, valueize))
> > +    return true;
> > +
> > +  if (gimple_nop_convert (expr2, &other, valueize)
> > +      && gimple_bitwise_inverted_equal_p (expr1, other, valueize))
> > +    return true;
> > +
> > +  if (TREE_CODE (expr1) != SSA_NAME
> > +      || TREE_CODE (expr2) != SSA_NAME)
> > +    return false;
> > +
> > +  gimple *d1 = get_def (valueize, expr1);
> > +  gassign *a1 = safe_dyn_cast <gassign *> (d1);
> > +  gimple *d2 = get_def (valueize, expr2);
> > +  gassign *a2 = safe_dyn_cast <gassign *> (d2);
> > +  if (a1
> > +      && gimple_assign_rhs_code (a1) == BIT_NOT_EXPR
> > +      && gimple_bitwise_equal_p (do_valueize (valueize,
> > +                                             gimple_assign_rhs1 (a1)),
> > +                                expr2, valueize))
> > +       return true;
> > +  if (a2
> > +      && gimple_assign_rhs_code (a2) == BIT_NOT_EXPR
> > +      && gimple_bitwise_equal_p (expr1,
> > +                                do_valueize (valueize,
> > +                                             gimple_assign_rhs1 (a2)),
> > +                                valueize))
> > +       return true;
> > +
> > +  if (a1 && a2
> > +      && TREE_CODE_CLASS (gimple_assign_rhs_code (a1)) == tcc_comparison
> > +      && TREE_CODE_CLASS (gimple_assign_rhs_code (a2)) == tcc_comparison)
> > +    {
> > +      tree op10 = gimple_assign_rhs1 (a1);
> > +      tree op20 = gimple_assign_rhs1 (a2);
> > +      if (!operand_equal_p (op10, op20))
> > +        return false;
> > +      tree op11 = gimple_assign_rhs2 (a1);
> > +      tree op21 = gimple_assign_rhs2 (a2);
> > +      if (!operand_equal_p (op11, op21))
> > +        return false;
> > +      if (invert_tree_comparison (gimple_assign_rhs_code (a1),
> > +                                 HONOR_NANS (op10))
> > +         == gimple_assign_rhs_code (a2))
> > +       return true;
> > +    }
> > +  return false;
> > +}
> > diff --git a/gcc/match.pd b/gcc/match.pd
> > index ee6cef6b09d..5fc6f517ab9 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -1943,8 +1943,9 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >   /* (~x | y) & x -> x & y */
> >   /* (~x & y) | x -> x | y */
> >   (simplify
> > -  (bitop:c (rbitop:c (bit_not @0) @1) @0)
> > -  (bitop @0 @1)))
> > +  (bitop:c (rbitop:c @2 @1) @0)
> > +  (if (bitwise_inverted_equal_p (@0, @2))
> > +   (bitop @0 @1))))
> >
> >  /* ((x | y) & z) | x -> (z & y) | x */
> >  (simplify
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitops-3.c b/gcc/testsuite/gcc.dg/tree-ssa/bitops-3.c
> > new file mode 100644
> > index 00000000000..bf11a129b69
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitops-3.c
> > @@ -0,0 +1,67 @@
> > +/* PR tree-optimization/100864 */
> > +
> > +/* { dg-do run } */
> > +/* { dg-options "-O1 -fdump-tree-optimized-raw" } */
> > +
> > +#define op_ne !=
> > +#define op_eq ==
> > +#define op_lt <
> > +#define op_le <=
> > +#define op_gt >
> > +#define op_ge >=
> > +
> > +#define operators(t) \
> > +t(ne) \
> > +t(eq) \
> > +t(lt) \
> > +t(le) \
> > +t(gt) \
> > +t(ge)
> > +
> > +#define cmpfunc(v, op) \
> > +__attribute__((noipa)) \
> > +_Bool func_##op##_##v(v int a, v int b, v _Bool e) \
> > +{ \
> > +  v _Bool c = (a op_##op b); \
> > +  v _Bool d = !c; \
> > +  return (e & d) | c; \
> > +}
> > +
> > +#define cmp_funcs(op) \
> > +cmpfunc(, op) \
> > +cmpfunc(volatile , op)
> > +
> > +operators(cmp_funcs)
> > +
> > +#define test(op) \
> > +if (func_##op##_ (a, b, e) != func_##op##_volatile (a, b, e)) \
> > + __builtin_abort();
> > +
> > +int main()
> > +{
> > +  for(int a = -3; a <= 3; a++)
> > +    for(int b = -3; b <= 3; b++)
> > +      {
> > +       _Bool e = 0;
> > +       operators(test)
> > +       e = 1;
> > +       operators(test)
> > +      }
> > +  return 0;
> > +}
> > +
> > +/* Check to make sure we optimize `(a&!b) | b` -> `a | b`. */
> > +/* There are 6 different comparison operators testing here. */
> > +/* bit_not_expr and bit_and_expr should show up for each one (volatile). */
> > +/* Each operator should show up twice
> > +   (except for `!=` which shows up 2*6 (each tester) + 2 (the 2 loops) extra = 16). */
> > +/* bit_ior_expr will show up for each operator twice (non-volatile and volatile). */
> > +/* { dg-final { scan-tree-dump-times "ne_expr,"      16 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "eq_expr,"       2 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "lt_expr,"       2 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "le_expr,"       2 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "gt_expr,"       2 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "ge_expr,"       2 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "bit_not_expr,"  6 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "bit_and_expr,"  6 "optimized"} } */
> > +/* { dg-final { scan-tree-dump-times "bit_ior_expr," 12 "optimized"} } */
> > --
> > 2.31.1
> >