* [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
@ 2023-07-31 17:07 Andrew Pinski
2023-08-02 17:11 ` Prathamesh Kulkarni
2023-08-03 11:57 ` Mikael Morin
0 siblings, 2 replies; 7+ messages in thread
From: Andrew Pinski @ 2023-07-31 17:07 UTC (permalink / raw)
To: gcc-patches; +Cc: Andrew Pinski
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.
---
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
2023-07-31 17:07 [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons Andrew Pinski
@ 2023-08-02 17:11 ` Prathamesh Kulkarni
2023-08-02 17:14 ` Andrew Pinski
2023-08-03 11:57 ` Mikael Morin
1 sibling, 1 reply; 7+ messages in thread
From: Prathamesh Kulkarni @ 2023-08-02 17:11 UTC (permalink / raw)
To: Andrew Pinski; +Cc: gcc-patches
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.
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
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
2023-08-02 17:11 ` Prathamesh Kulkarni
@ 2023-08-02 17:14 ` Andrew Pinski
2023-08-02 21:23 ` Andrew Pinski
0 siblings, 1 reply; 7+ messages in thread
From: Andrew Pinski @ 2023-08-02 17:14 UTC (permalink / raw)
To: Prathamesh Kulkarni; +Cc: Andrew Pinski, gcc-patches
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
> >
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
2023-08-02 17:14 ` Andrew Pinski
@ 2023-08-02 21:23 ` Andrew Pinski
2023-08-03 8:07 ` Prathamesh Kulkarni
0 siblings, 1 reply; 7+ messages in thread
From: Andrew Pinski @ 2023-08-02 21:23 UTC (permalink / raw)
To: Prathamesh Kulkarni; +Cc: Andrew Pinski, gcc-patches
On Wed, Aug 2, 2023 at 10:14 AM Andrew Pinski <pinskia@gmail.com> wrote:
>
> 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.
Yes the issue is the same and is solved by the same patch.
Thanks,
Andrew
>
> 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
> > >
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
2023-08-02 21:23 ` Andrew Pinski
@ 2023-08-03 8:07 ` Prathamesh Kulkarni
0 siblings, 0 replies; 7+ messages in thread
From: Prathamesh Kulkarni @ 2023-08-03 8:07 UTC (permalink / raw)
To: Andrew Pinski; +Cc: Andrew Pinski, gcc-patches
On Thu, 3 Aug 2023 at 02:54, Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Wed, Aug 2, 2023 at 10:14 AM Andrew Pinski <pinskia@gmail.com> wrote:
> >
> > 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.
>
> Yes the issue is the same and is solved by the same patch.
That's great, thanks for the heads up!
Thanks,
Prathamesh
>
> Thanks,
> Andrew
>
> >
> > 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
> > > >
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
2023-07-31 17:07 [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons Andrew Pinski
2023-08-02 17:11 ` Prathamesh Kulkarni
@ 2023-08-03 11:57 ` Mikael Morin
2023-08-03 15:34 ` Andrew Pinski
1 sibling, 1 reply; 7+ messages in thread
From: Mikael Morin @ 2023-08-03 11:57 UTC (permalink / raw)
To: Andrew Pinski, gcc-patches
Hello,
Le 31/07/2023 à 19:07, Andrew Pinski via Gcc-patches a écrit :
> 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;
So this is trying to match a == b against a != b, or a < b against a >=
b, or similar; correct?
Shouldn't this be completed with "crossed" checks, that is match a == b
against b != a, or a < b against b <= a, etc? Or is there some
canonicalization making that redundant?
I have given up determining whether these cases were already covered by
the test or not.
Mikael
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons
2023-08-03 11:57 ` Mikael Morin
@ 2023-08-03 15:34 ` Andrew Pinski
0 siblings, 0 replies; 7+ messages in thread
From: Andrew Pinski @ 2023-08-03 15:34 UTC (permalink / raw)
To: Mikael Morin; +Cc: Andrew Pinski, gcc-patches
On Thu, Aug 3, 2023 at 4:58 AM Mikael Morin <morin-mikael@orange.fr> wrote:
>
> Hello,
>
> Le 31/07/2023 à 19:07, Andrew Pinski via Gcc-patches a écrit :
> > 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;
>
> So this is trying to match a == b against a != b, or a < b against a >=
> b, or similar; correct?
> Shouldn't this be completed with "crossed" checks, that is match a == b
> against b != a, or a < b against b <= a, etc? Or is there some
> canonicalization making that redundant?
There is some canonicalization that does happen so you don't need to
do the cross checking.
tree_swap_operands_p defines that order .
In that the lower ssa names are always first operands and constants
are always last.
Thanks,
Andrew
>
> I have given up determining whether these cases were already covered by
> the test or not.
>
> Mikael
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2023-08-03 15:34 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-31 17:07 [COMMITTEDv3] tree-optimization: [PR100864] `(a&!b) | b` is not opimized to `a | b` for comparisons Andrew Pinski
2023-08-02 17:11 ` Prathamesh Kulkarni
2023-08-02 17:14 ` Andrew Pinski
2023-08-02 21:23 ` Andrew Pinski
2023-08-03 8:07 ` Prathamesh Kulkarni
2023-08-03 11:57 ` Mikael Morin
2023-08-03 15:34 ` Andrew Pinski
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).