Fold more boolean expressions

Message ID trinity-a72ca4d5-53d7-47f9-9609-c54c00e9a0a2-1536674038993@3c-app-mailcom-bs11
State New
Headers show
Series
  • Fold more boolean expressions
Related show

Commit Message

MCC CS Sept. 11, 2018, 1:53 p.m.
Hi everyone,

this patch optimizes a few boolean expressions,
and fixes some unneeded whitespace.
Will do a full make check soon.
 
Thanks for your time.

2018-09-11 MCC CS <deswurstes@users.noreply.github.com>

	gcc/
	PR tree-optimization/87261
	* match.pd: Add boolean optimizations,
	fix whitespace.

2018-09-11 MCC CS <deswurstes@users.noreply.github.com>

	gcc/testsuite/
	PR tree-optimization/87261
	* gcc.dg/pr87261.c: New test.

Comments

Marc Glisse Sept. 11, 2018, 9:24 p.m. | #1
(just some very quick comments, they may be off, and I haven't looked 
closely)

On Tue, 11 Sep 2018, MCC CS wrote:

> +/* (~x & y) | ~(x | y) -> ~x */

> +(simplify

> + (bit_ior:c (bit_and:c (bit_not @0) @1) (bit_not (bit_ior:s @0 @1)))

> + (bit_not @0))


Did you mean :c instead of :s?
You should write (bit_not@2 @0) in the input, then the output can be just 
@2.

> +/* (x | y) ^ (x | ~y) -> ~x */

> +(simplify

> + (bit_xor:c (bit_ior:s @0 @1) (bit_ior:c @0 (bit_not @1)))

> + (bit_not @0))


:s -> :c again?

> +/* (x & y) | ~(x | y) -> ~(x ^ y) */

> +(simplify

> + (bit_ior:c (bit_and:s @0 @1) (bit_not (bit_ior:s @0 @1)))

> + (bit_not (bit_xor @0 @1)))


Probably add :s to bit_not as well?

> +/* (~x | y) ^ (x ^ y) -> x | ~y */

> +(simplify

> + (bit_xor:c (bit_ior:c (bit_not @0) @1) (bit_xor:s @0 @1))

> + (bit_ior @0 (bit_not @1)))


:c on the last bit_xor.
If we have some :s, having one just on the last bit_xor seems strange.

> +/* (x ^ y) | ~(x | y) -> ~(x & y) */

> +(simplify

> + (bit_ior:c (bit_xor:s @0 @1) (bit_not (bit_ior:s @0 @1)))

> + (bit_not (bit_and @0 @1)))


bit_not:s

-- 
Marc Glisse
MCC CS Sept. 14, 2018, 3:32 p.m. | #2
Thanks for the review! I've cleaned up the :s and :c flags.
You can see the changes here: https://www.diffchecker.com/sjNOq5TQ

Anyone else have time for another review? Would be really
appreciated.

2018-09-14 MCC CS <deswurstes@users.noreply.github.com>

	gcc/
	PR tree-optimization/87261
	* match.pd: Add boolean optimizations,
	fix whitespace.

2018-09-14 MCC CS <deswurstes@users.noreply.github.com>

	gcc/testsuite/
	PR tree-optimization/87261
	* gcc.dg/pr87261.c: New test.

Index: gcc/match.pd
===================================================================
--- gcc/match.pd (revision 264170)
+++ gcc/match.pd (working copy)
@@ -92,7 +92,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)
(define_operator_list COND_TERNARY
IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)
-
+
/* As opposed to convert?, this still creates a single pattern, so
it is not a suitable replacement for convert? in all cases. */
(match (nop_convert @0)
@@ -106,7 +106,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
/* This one has to be last, or it shadows the others. */
(match (nop_convert @0)
- @0)
+ @0)

/* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
ABSU_EXPR returns unsigned absolute value of the operand and the operand
@@ -285,7 +285,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
And not for _Fract types where we can't build 1. */
(if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))
{ build_one_cst (type); }))
- /* X / abs (X) is X < 0 ? -1 : 1. */
+ /* X / abs (X) is X < 0 ? -1 : 1. */
(simplify
(div:C @0 (abs @0))
(if (INTEGRAL_TYPE_P (type)
@@ -921,6 +921,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(bitop:c @0 (bit_not (bitop:cs @0 @1)))
(bitop @0 (bit_not @1))))

+/* (~x & y) | ~(x | y) -> ~x */
+(simplify
+ (bit_ior:c (bit_and:c (bit_not @0) @1) (bit_not (bit_ior:c @0 @1)))
+ (bit_not @0))
+
+/* (x | y) ^ (x | ~y) -> ~x */
+(simplify
+ (bit_xor:c (bit_ior:c @0 @1) (bit_ior:c @0 (bit_not @1)))
+ (bit_not @0))
+
+/* (x & y) | ~(x | y) -> ~(x ^ y) */
+(simplify
+ (bit_ior:c (bit_and @0 @1) (bit_not:s (bit_ior:s @0 @1)))
+ (bit_not (bit_xor @0 @1)))
+
+/* (~x | y) ^ (x ^ y) -> x | ~y */
+(simplify
+ (bit_xor:c (bit_ior:cs (bit_not @0) @1) (bit_xor:c @0 @1))
+ (bit_ior @0 (bit_not @1)))
+
+/* (x ^ y) | ~(x | y) -> ~(x & y) */
+(simplify
+ (bit_ior:c (bit_xor @0 @1) (bit_not:s (bit_ior @0 @1)))
+ (bit_not (bit_and @0 @1)))
+
/* (x | y) & ~x -> y & ~x */
/* (x & y) | ~x -> y | ~x */
(for bitop (bit_and bit_ior)
@@ -1131,7 +1156,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (tree_nop_conversion_p (type, TREE_TYPE (@0))
&& tree_nop_conversion_p (type, TREE_TYPE (@1)))
(mult (convert @0) (convert (negate @1)))))
-
+
/* -(A + B) -> (-B) - A. */
(simplify
(negate (plus:c @0 negate_expr_p@1))
@@ -3091,7 +3116,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (tree_int_cst_sgn (@1) < 0)
(scmp @0 @2)
(cmp @0 @2))))))
-
+
/* Simplify comparison of something with itself. For IEEE
floating-point, we can only do some of these simplifications. */
(for cmp (eq ge le)
@@ -3162,11 +3187,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
}
tree newtype
= (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (type1)
- ? TREE_TYPE (@0) : type1);
+ ? TREE_TYPE (@0) : type1);
}
(if (TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (newtype))
(cmp (convert:newtype @0) (convert:newtype @1))))))
-
+
(simplify
(cmp @0 REAL_CST@1)
/* IEEE doesn't distinguish +0 and -0 in comparisons. */
@@ -3414,7 +3439,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(FTYPE) N == CST -> 0
(FTYPE) N != CST -> 1. */
(if (cmp == EQ_EXPR || cmp == NE_EXPR)
- { constant_boolean_node (cmp == NE_EXPR, type); })
+ { constant_boolean_node (cmp == NE_EXPR, type); })
/* Otherwise replace with sensible integer constant. */
(with
{
@@ -3656,7 +3681,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(simplify
(cmp (bit_and@2 @0 integer_pow2p@1) @1)
(icmp @2 { build_zero_cst (TREE_TYPE (@0)); })))
-
+
/* If we have (A & C) != 0 ? D : 0 where C and D are powers of 2,
convert this into a shift followed by ANDing with D. */
(simplify
@@ -3876,7 +3901,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (cmp == LE_EXPR)
(ge (convert:st @0) { build_zero_cst (st); })
(lt (convert:st @0) { build_zero_cst (st); }))))))))))
-
+
(for cmp (unordered ordered unlt unle ungt unge uneq ltgt)
/* If the second operand is NaN, the result is constant. */
(simplify
@@ -4530,7 +4555,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (wi::to_wide (@1) == -1)
(rdiv { build_real (type, dconst1); } @0))))

-/* Narrowing of arithmetic and logical operations.
+/* Narrowing of arithmetic and logical operations.

These are conceptually similar to the transformations performed for
the C/C++ front-ends by shorten_binary_op and shorten_compare. Long
@@ -4602,7 +4627,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(convert (bit_and (op (convert:utype @0) (convert:utype @1))
(convert:utype @4))))))))

-/* Transform (@0 < @1 and @0 < @2) to use min,
+/* Transform (@0 < @1 and @0 < @2) to use min,
(@0 > @1 and @0 > @2) to use max */
(for logic (bit_and bit_and bit_and bit_and bit_ior bit_ior bit_ior bit_ior)
op (lt le gt ge lt le gt ge )
Index: gcc/testsuite/gcc.dg/pr87261.c
===================================================================
--- gcc/testsuite/gcc.dg/pr87261.c (nonexistent)
+++ gcc/testsuite/gcc.dg/pr87261.c (working copy)
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-original" } */
+
+int f1 (int a, int b)
+{
+ return ~(a|b)|(~a&b);
+}
+
+int f2 (int a, int b)
+{
+ return (a|b)^(a|~b);
+}
+
+/* { dg-final { scan-tree-dump-times "return \\~a;" 2 "original" } } */
+
+int f3 (int a, int b)
+{
+ return ~(a|b)|(a&b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\^ b\\);" "original" } } */
+
+int f4 (int a, int b)
+{
+ return a^b^(~a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~b \\| a;" "original" } } */
+
+int f5 (int a, int b)
+{
+ return (a^b)|~(a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\& b\\);" "original" } } */
Marc Glisse Sept. 14, 2018, 4:38 p.m. | #3
On Fri, 14 Sep 2018, MCC CS wrote:

> +/* (~x & y) | ~(x | y) -> ~x */

> +(simplify

> + (bit_ior:c (bit_and:c (bit_not @0) @1) (bit_not (bit_ior:c @0 @1)))

> + (bit_not @0))


As I said last time, you should not generate a new (bit_not @0) in the 
output when there is already one in the input. Maybe

(simplify
  (bit_ior:c (bit_and:c (bit_not@2 @0) @1) (bit_not (bit_ior:c @0 @1)))
  @2)

-- 
Marc Glisse
MCC CS Sept. 15, 2018, 6 a.m. | #4
Sorry for doing the same mistake twice. Is this OK, and do
I need to test it again after the first version of this
patch?

2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

	gcc/
	PR tree-optimization/87261
	* match.pd: Add boolean optimizations,
	fix whitespace.

2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

	gcc/testsuite/
	PR tree-optimization/87261
	* gcc.dg/pr87261.c: New test.

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 264170)
+++ gcc/match.pd	(working copy)
@@ -92,7 +92,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)
 (define_operator_list COND_TERNARY
   IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)
-    
+
 /* As opposed to convert?, this still creates a single pattern, so
    it is not a suitable replacement for convert? in all cases.  */
 (match (nop_convert @0)
@@ -106,7 +106,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
 /* This one has to be last, or it shadows the others.  */
 (match (nop_convert @0)
- @0) 
+ @0)
 
 /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
    ABSU_EXPR returns unsigned absolute value of the operand and the operand
@@ -285,7 +285,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      And not for _Fract types where we can't build 1.  */
   (if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))
    { build_one_cst (type); }))
- /* X / abs (X) is X < 0 ? -1 : 1.  */ 
+ /* X / abs (X) is X < 0 ? -1 : 1.  */
  (simplify
    (div:C @0 (abs @0))
    (if (INTEGRAL_TYPE_P (type)
@@ -921,6 +921,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (bitop:c @0 (bit_not (bitop:cs @0 @1)))
   (bitop @0 (bit_not @1))))
 
+/* (~x & y) | ~(x | y) -> ~x */
+(simplify
+ (bit_ior:c (bit_and:c (bit_not@2 @0) @1) (bit_not (bit_ior:c @0 @1)))
+ @2)
+
+/* (x | y) ^ (x | ~y) -> ~x */
+(simplify
+ (bit_xor:c (bit_ior:c @0 @1) (bit_ior:c @0 (bit_not @1)))
+ (bit_not @0))
+
+/* (x & y) | ~(x | y) -> ~(x ^ y) */
+(simplify
+ (bit_ior:c (bit_and @0 @1) (bit_not:s (bit_ior:s @0 @1)))
+ (bit_not (bit_xor @0 @1)))
+
+/* (~x | y) ^ (x ^ y) -> x | ~y */
+(simplify
+ (bit_xor:c (bit_ior:cs (bit_not @0) @1) (bit_xor:c @0 @1))
+ (bit_ior @0 (bit_not @1)))
+
+/* (x ^ y) | ~(x | y) -> ~(x & y) */
+(simplify
+ (bit_ior:c (bit_xor @0 @1) (bit_not:s (bit_ior @0 @1)))
+ (bit_not (bit_and @0 @1)))
+
 /* (x | y) & ~x -> y & ~x */
 /* (x & y) | ~x -> y | ~x */
 (for bitop (bit_and bit_ior)
@@ -1131,7 +1156,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
        && tree_nop_conversion_p (type, TREE_TYPE (@1)))
    (mult (convert @0) (convert (negate @1)))))
- 
+
 /* -(A + B) -> (-B) - A.  */
 (simplify
  (negate (plus:c @0 negate_expr_p@1))
@@ -3091,7 +3116,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (if (tree_int_cst_sgn (@1) < 0)
      (scmp @0 @2)
      (cmp @0 @2))))))
- 
+
 /* Simplify comparison of something with itself.  For IEEE
    floating-point, we can only do some of these simplifications.  */
 (for cmp (eq ge le)
@@ -3162,11 +3187,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
         }
       tree newtype
         = (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (type1)
-	   ? TREE_TYPE (@0) : type1); 
+	   ? TREE_TYPE (@0) : type1);
     }
     (if (TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (newtype))
      (cmp (convert:newtype @0) (convert:newtype @1))))))
- 
+
  (simplify
   (cmp @0 REAL_CST@1)
   /* IEEE doesn't distinguish +0 and -0 in comparisons.  */
@@ -3414,7 +3439,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	    (FTYPE) N == CST -> 0
 	    (FTYPE) N != CST -> 1.  */
 	(if (cmp == EQ_EXPR || cmp == NE_EXPR)
-	 { constant_boolean_node (cmp == NE_EXPR, type); }) 
+	 { constant_boolean_node (cmp == NE_EXPR, type); })
 	/* Otherwise replace with sensible integer constant.  */
 	(with
 	 {
@@ -3656,7 +3681,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (simplify
   (cmp (bit_and@2 @0 integer_pow2p@1) @1)
   (icmp @2 { build_zero_cst (TREE_TYPE (@0)); })))
- 
+
 /* If we have (A & C) != 0 ? D : 0 where C and D are powers of 2,
    convert this into a shift followed by ANDing with D.  */
 (simplify
@@ -3876,7 +3901,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
         (if (cmp == LE_EXPR)
 	 (ge (convert:st @0) { build_zero_cst (st); })
 	 (lt (convert:st @0) { build_zero_cst (st); }))))))))))
- 
+
 (for cmp (unordered ordered unlt unle ungt unge uneq ltgt)
  /* If the second operand is NaN, the result is constant.  */
  (simplify
@@ -4530,7 +4555,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (wi::to_wide (@1) == -1)
    (rdiv { build_real (type, dconst1); } @0))))
 
-/* Narrowing of arithmetic and logical operations. 
+/* Narrowing of arithmetic and logical operations.
 
    These are conceptually similar to the transformations performed for
    the C/C++ front-ends by shorten_binary_op and shorten_compare.  Long
@@ -4602,7 +4627,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      (convert (bit_and (op (convert:utype @0) (convert:utype @1))
 	       (convert:utype @4))))))))
 
-/* Transform (@0 < @1 and @0 < @2) to use min, 
+/* Transform (@0 < @1 and @0 < @2) to use min,
    (@0 > @1 and @0 > @2) to use max */
 (for logic (bit_and bit_and bit_and bit_and bit_ior bit_ior bit_ior bit_ior)
      op    (lt      le      gt      ge      lt      le      gt      ge     )
Index: gcc/testsuite/gcc.dg/pr87261.c
===================================================================
--- gcc/testsuite/gcc.dg/pr87261.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/pr87261.c	(working copy)
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-original" } */
+
+int f1 (int a, int b)
+{
+ return ~(a|b)|(~a&b);
+}
+
+int f2 (int a, int b)
+{
+ return (a|b)^(a|~b);
+}
+
+/* { dg-final { scan-tree-dump-times "return \\~a;" 2 "original" } } */
+
+int f3 (int a, int b)
+{
+ return ~(a|b)|(a&b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\^ b\\);" "original" } } */
+
+int f4 (int a, int b)
+{
+ return a^b^(~a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~b \\| a;" "original" } } */
+
+int f5 (int a, int b)
+{
+ return (a^b)|~(a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\& b\\);" "original" } } */
MCC CS Sept. 16, 2018, 4:58 p.m. | #5
Hi, I have bootstrapped and make check'd my final patch
on latest trunk. Is it OK? Could you please push it
if possible?

The patch can be found here, but please update the commit
message date:
https://gcc.gnu.org/ml/gcc-patches/2018-09/msg00803.html

Test result:

Native configuration is x86_64-pc-linux-gnu

		=== gcc tests ===


Running target unix

		=== gcc Summary ===

# of expected passes		134514
# of expected failures		462
# of unsupported tests		2109
/home/usr/Desktop/gcc-build/gcc/xgcc  version 9.0.0 20180916 (experimental) (GCC) 

		=== g++ tests ===


Running target unix
FAIL: g++.dg/pr80481.C  -std=gnu++98  scan-assembler-not vmovaps
FAIL: g++.dg/pr80481.C  -std=gnu++11  scan-assembler-not vmovaps
FAIL: g++.dg/pr80481.C  -std=gnu++14  scan-assembler-not vmovaps
FAIL: g++.dg/pr83239.C  -std=gnu++98 (test for excess errors)

		=== g++ Summary ===

# of expected passes		127011
# of unexpected failures	4
# of expected failures		532
# of unsupported tests		5028
/home/usr/Desktop/gcc-build/gcc/xg++  version 9.0.0 20180916 (experimental) (GCC) 

		=== libatomic tests ===


Running target unix

		=== libatomic Summary ===

# of expected passes		54
		=== libgomp tests ===


Running target unix

		=== libgomp Summary ===

# of expected passes		2031
# of expected failures		1
# of unsupported tests		188
		=== libitm tests ===


Running target unix

		=== libitm Summary ===

# of expected passes		42
# of expected failures		3
# of unsupported tests		1
		=== libstdc++ tests ===


Running target unix

		=== libstdc++ Summary ===

# of expected passes		12667
# of expected failures		77
# of unsupported tests		589

Compiler version: 9.0.020180916(experimental)(GCC) 
Platform: x86_64-pc-linux-gnu
configure flags: --enable-languages=c,c++ --prefix=/home/usr/Desktop/gcc-out --with-system-zlib --enable-checking=release --disable-multilib --with-abi=m64
Richard Biener Sept. 20, 2018, 1:09 p.m. | #6
On Sat, Sep 15, 2018 at 8:01 AM MCC CS <mcccs@gmx.com> wrote:
>

> Sorry for doing the same mistake twice. Is this OK, and do

> I need to test it again after the first version of this

> patch?

>

> 2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

>

>         gcc/

>         PR tree-optimization/87261

>         * match.pd: Add boolean optimizations,

>         fix whitespace.

>

> 2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

>

>         gcc/testsuite/

>         PR tree-optimization/87261

>         * gcc.dg/pr87261.c: New test.

>

> Index: gcc/match.pd

> ===================================================================

> --- gcc/match.pd        (revision 264170)

> +++ gcc/match.pd        (working copy)

> @@ -92,7 +92,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>    IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)

>  (define_operator_list COND_TERNARY

>    IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)

> -

> +

>  /* As opposed to convert?, this still creates a single pattern, so

>     it is not a suitable replacement for convert? in all cases.  */

>  (match (nop_convert @0)

> @@ -106,7 +106,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>        && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))

>  /* This one has to be last, or it shadows the others.  */

>  (match (nop_convert @0)

> - @0)

> + @0)

>

>  /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>

>     ABSU_EXPR returns unsigned absolute value of the operand and the operand

> @@ -285,7 +285,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>       And not for _Fract types where we can't build 1.  */

>    (if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))

>     { build_one_cst (type); }))

> - /* X / abs (X) is X < 0 ? -1 : 1.  */

> + /* X / abs (X) is X < 0 ? -1 : 1.  */

>   (simplify

>     (div:C @0 (abs @0))

>     (if (INTEGRAL_TYPE_P (type)

> @@ -921,6 +921,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>    (bitop:c @0 (bit_not (bitop:cs @0 @1)))

>    (bitop @0 (bit_not @1))))

>

> +/* (~x & y) | ~(x | y) -> ~x */

> +(simplify

> + (bit_ior:c (bit_and:c (bit_not@2 @0) @1) (bit_not (bit_ior:c @0 @1)))

> + @2)

> +

> +/* (x | y) ^ (x | ~y) -> ~x */

> +(simplify

> + (bit_xor:c (bit_ior:c @0 @1) (bit_ior:c @0 (bit_not @1)))

> + (bit_not @0))

> +

> +/* (x & y) | ~(x | y) -> ~(x ^ y) */

> +(simplify

> + (bit_ior:c (bit_and @0 @1) (bit_not:s (bit_ior:s @0 @1)))


I think this misses :cs on the bit_and.

> + (bit_not (bit_xor @0 @1)))

> +

> +/* (~x | y) ^ (x ^ y) -> x | ~y */

> +(simplify

> + (bit_xor:c (bit_ior:cs (bit_not @0) @1) (bit_xor:c @0 @1))

> + (bit_ior @0 (bit_not @1)))


:s on the bit_xor

> +/* (x ^ y) | ~(x | y) -> ~(x & y) */

> +(simplify

> + (bit_ior:c (bit_xor @0 @1) (bit_not:s (bit_ior @0 @1)))

> + (bit_not (bit_and @0 @1)))


:cs on the bit_xor, :s on the second bit_ior

Otherwise looks OK to me.

Thanks,
Richard.

>  /* (x | y) & ~x -> y & ~x */

>  /* (x & y) | ~x -> y | ~x */

>  (for bitop (bit_and bit_ior)

> @@ -1131,7 +1156,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>    (if (tree_nop_conversion_p (type, TREE_TYPE (@0))

>         && tree_nop_conversion_p (type, TREE_TYPE (@1)))

>     (mult (convert @0) (convert (negate @1)))))

> -

> +

>  /* -(A + B) -> (-B) - A.  */

>  (simplify

>   (negate (plus:c @0 negate_expr_p@1))

> @@ -3091,7 +3116,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>      (if (tree_int_cst_sgn (@1) < 0)

>       (scmp @0 @2)

>       (cmp @0 @2))))))

> -

> +

>  /* Simplify comparison of something with itself.  For IEEE

>     floating-point, we can only do some of these simplifications.  */

>  (for cmp (eq ge le)

> @@ -3162,11 +3187,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>          }

>        tree newtype

>          = (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (type1)

> -          ? TREE_TYPE (@0) : type1);

> +          ? TREE_TYPE (@0) : type1);

>      }

>      (if (TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (newtype))

>       (cmp (convert:newtype @0) (convert:newtype @1))))))

> -

> +

>   (simplify

>    (cmp @0 REAL_CST@1)

>    /* IEEE doesn't distinguish +0 and -0 in comparisons.  */

> @@ -3414,7 +3439,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>             (FTYPE) N == CST -> 0

>             (FTYPE) N != CST -> 1.  */

>         (if (cmp == EQ_EXPR || cmp == NE_EXPR)

> -        { constant_boolean_node (cmp == NE_EXPR, type); })

> +        { constant_boolean_node (cmp == NE_EXPR, type); })

>         /* Otherwise replace with sensible integer constant.  */

>         (with

>          {

> @@ -3656,7 +3681,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>   (simplify

>    (cmp (bit_and@2 @0 integer_pow2p@1) @1)

>    (icmp @2 { build_zero_cst (TREE_TYPE (@0)); })))

> -

> +

>  /* If we have (A & C) != 0 ? D : 0 where C and D are powers of 2,

>     convert this into a shift followed by ANDing with D.  */

>  (simplify

> @@ -3876,7 +3901,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>          (if (cmp == LE_EXPR)

>          (ge (convert:st @0) { build_zero_cst (st); })

>          (lt (convert:st @0) { build_zero_cst (st); }))))))))))

> -

> +

>  (for cmp (unordered ordered unlt unle ungt unge uneq ltgt)

>   /* If the second operand is NaN, the result is constant.  */

>   (simplify

> @@ -4530,7 +4555,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>    (if (wi::to_wide (@1) == -1)

>     (rdiv { build_real (type, dconst1); } @0))))

>

> -/* Narrowing of arithmetic and logical operations.

> +/* Narrowing of arithmetic and logical operations.

>

>     These are conceptually similar to the transformations performed for

>     the C/C++ front-ends by shorten_binary_op and shorten_compare.  Long

> @@ -4602,7 +4627,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>       (convert (bit_and (op (convert:utype @0) (convert:utype @1))

>                (convert:utype @4))))))))

>

> -/* Transform (@0 < @1 and @0 < @2) to use min,

> +/* Transform (@0 < @1 and @0 < @2) to use min,

>     (@0 > @1 and @0 > @2) to use max */

>  (for logic (bit_and bit_and bit_and bit_and bit_ior bit_ior bit_ior bit_ior)

>       op    (lt      le      gt      ge      lt      le      gt      ge     )

> Index: gcc/testsuite/gcc.dg/pr87261.c

> ===================================================================

> --- gcc/testsuite/gcc.dg/pr87261.c      (nonexistent)

> +++ gcc/testsuite/gcc.dg/pr87261.c      (working copy)

> @@ -0,0 +1,35 @@

> +/* { dg-do compile } */

> +/* { dg-options "-O -fdump-tree-original" } */

> +

> +int f1 (int a, int b)

> +{

> + return ~(a|b)|(~a&b);

> +}

> +

> +int f2 (int a, int b)

> +{

> + return (a|b)^(a|~b);

> +}

> +

> +/* { dg-final { scan-tree-dump-times "return \\~a;" 2 "original" } } */

> +

> +int f3 (int a, int b)

> +{

> + return ~(a|b)|(a&b);

> +}

> +

> +/* { dg-final { scan-tree-dump "return \\~\\(a \\^ b\\);" "original" } } */

> +

> +int f4 (int a, int b)

> +{

> + return a^b^(~a|b);

> +}

> +

> +/* { dg-final { scan-tree-dump "return \\~b \\| a;" "original" } } */

> +

> +int f5 (int a, int b)

> +{

> + return (a^b)|~(a|b);

> +}

> +

> +/* { dg-final { scan-tree-dump "return \\~\\(a \\& b\\);" "original" } } */
Marc Glisse Sept. 20, 2018, 2 p.m. | #7
On Thu, 20 Sep 2018, Richard Biener wrote:

> On Sat, Sep 15, 2018 at 8:01 AM MCC CS <mcccs@gmx.com> wrote:

>>

>> Sorry for doing the same mistake twice. Is this OK, and do

>> I need to test it again after the first version of this

>> patch?

>>

>> 2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

>>

>>         gcc/

>>         PR tree-optimization/87261

>>         * match.pd: Add boolean optimizations,

>>         fix whitespace.

>>

>> 2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

>>

>>         gcc/testsuite/

>>         PR tree-optimization/87261

>>         * gcc.dg/pr87261.c: New test.

>>

>> Index: gcc/match.pd

>> ===================================================================

>> --- gcc/match.pd        (revision 264170)

>> +++ gcc/match.pd        (working copy)

>> @@ -92,7 +92,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>>    IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)

>>  (define_operator_list COND_TERNARY

>>    IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)

>> -

>> +

>>  /* As opposed to convert?, this still creates a single pattern, so

>>     it is not a suitable replacement for convert? in all cases.  */

>>  (match (nop_convert @0)

>> @@ -106,7 +106,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>>        && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))

>>  /* This one has to be last, or it shadows the others.  */

>>  (match (nop_convert @0)

>> - @0)

>> + @0)

>>

>>  /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>

>>     ABSU_EXPR returns unsigned absolute value of the operand and the operand

>> @@ -285,7 +285,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>>       And not for _Fract types where we can't build 1.  */

>>    (if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))

>>     { build_one_cst (type); }))

>> - /* X / abs (X) is X < 0 ? -1 : 1.  */

>> + /* X / abs (X) is X < 0 ? -1 : 1.  */

>>   (simplify

>>     (div:C @0 (abs @0))

>>     (if (INTEGRAL_TYPE_P (type)

>> @@ -921,6 +921,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

>>    (bitop:c @0 (bit_not (bitop:cs @0 @1)))

>>    (bitop @0 (bit_not @1))))

>>

>> +/* (~x & y) | ~(x | y) -> ~x */

>> +(simplify

>> + (bit_ior:c (bit_and:c (bit_not@2 @0) @1) (bit_not (bit_ior:c @0 @1)))

>> + @2)

>> +

>> +/* (x | y) ^ (x | ~y) -> ~x */

>> +(simplify

>> + (bit_xor:c (bit_ior:c @0 @1) (bit_ior:c @0 (bit_not @1)))

>> + (bit_not @0))

>> +

>> +/* (x & y) | ~(x | y) -> ~(x ^ y) */

>> +(simplify

>> + (bit_ior:c (bit_and @0 @1) (bit_not:s (bit_ior:s @0 @1)))

>

> I think this misses :cs on the bit_and.


For :c, shouldn't canonicalization make the order of @0 and @1 consistent 
for bit_and and bit_ior?

>> + (bit_not (bit_xor @0 @1)))

>> +

>> +/* (~x | y) ^ (x ^ y) -> x | ~y */

>> +(simplify

>> + (bit_xor:c (bit_ior:cs (bit_not @0) @1) (bit_xor:c @0 @1))

>> + (bit_ior @0 (bit_not @1)))

>

> :s on the bit_xor

>

>> +/* (x ^ y) | ~(x | y) -> ~(x & y) */

>> +(simplify

>> + (bit_ior:c (bit_xor @0 @1) (bit_not:s (bit_ior @0 @1)))

>> + (bit_not (bit_and @0 @1)))

>

> :cs on the bit_xor, :s on the second bit_ior

>

> Otherwise looks OK to me.


-- 
Marc Glisse
Richard Biener Sept. 20, 2018, 2:13 p.m. | #8
On Thu, Sep 20, 2018 at 4:00 PM Marc Glisse <marc.glisse@inria.fr> wrote:
>

> On Thu, 20 Sep 2018, Richard Biener wrote:

>

> > On Sat, Sep 15, 2018 at 8:01 AM MCC CS <mcccs@gmx.com> wrote:

> >>

> >> Sorry for doing the same mistake twice. Is this OK, and do

> >> I need to test it again after the first version of this

> >> patch?

> >>

> >> 2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

> >>

> >>         gcc/

> >>         PR tree-optimization/87261

> >>         * match.pd: Add boolean optimizations,

> >>         fix whitespace.

> >>

> >> 2018-09-15 MCC CS <deswurstes@users.noreply.github.com>

> >>

> >>         gcc/testsuite/

> >>         PR tree-optimization/87261

> >>         * gcc.dg/pr87261.c: New test.

> >>

> >> Index: gcc/match.pd

> >> ===================================================================

> >> --- gcc/match.pd        (revision 264170)

> >> +++ gcc/match.pd        (working copy)

> >> @@ -92,7 +92,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

> >>    IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)

> >>  (define_operator_list COND_TERNARY

> >>    IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)

> >> -

> >> +

> >>  /* As opposed to convert?, this still creates a single pattern, so

> >>     it is not a suitable replacement for convert? in all cases.  */

> >>  (match (nop_convert @0)

> >> @@ -106,7 +106,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

> >>        && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))

> >>  /* This one has to be last, or it shadows the others.  */

> >>  (match (nop_convert @0)

> >> - @0)

> >> + @0)

> >>

> >>  /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>

> >>     ABSU_EXPR returns unsigned absolute value of the operand and the operand

> >> @@ -285,7 +285,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

> >>       And not for _Fract types where we can't build 1.  */

> >>    (if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))

> >>     { build_one_cst (type); }))

> >> - /* X / abs (X) is X < 0 ? -1 : 1.  */

> >> + /* X / abs (X) is X < 0 ? -1 : 1.  */

> >>   (simplify

> >>     (div:C @0 (abs @0))

> >>     (if (INTEGRAL_TYPE_P (type)

> >> @@ -921,6 +921,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)

> >>    (bitop:c @0 (bit_not (bitop:cs @0 @1)))

> >>    (bitop @0 (bit_not @1))))

> >>

> >> +/* (~x & y) | ~(x | y) -> ~x */

> >> +(simplify

> >> + (bit_ior:c (bit_and:c (bit_not@2 @0) @1) (bit_not (bit_ior:c @0 @1)))

> >> + @2)

> >> +

> >> +/* (x | y) ^ (x | ~y) -> ~x */

> >> +(simplify

> >> + (bit_xor:c (bit_ior:c @0 @1) (bit_ior:c @0 (bit_not @1)))

> >> + (bit_not @0))

> >> +

> >> +/* (x & y) | ~(x | y) -> ~(x ^ y) */

> >> +(simplify

> >> + (bit_ior:c (bit_and @0 @1) (bit_not:s (bit_ior:s @0 @1)))

> >

> > I think this misses :cs on the bit_and.

>

> For :c, shouldn't canonicalization make the order of @0 and @1 consistent

> for bit_and and bit_ior?


Hmm, probably yes.  This all makes me think that the :c should better be
placed automagically by genmatch...

> >> + (bit_not (bit_xor @0 @1)))

> >> +

> >> +/* (~x | y) ^ (x ^ y) -> x | ~y */

> >> +(simplify

> >> + (bit_xor:c (bit_ior:cs (bit_not @0) @1) (bit_xor:c @0 @1))

> >> + (bit_ior @0 (bit_not @1)))

> >

> > :s on the bit_xor

> >

> >> +/* (x ^ y) | ~(x | y) -> ~(x & y) */

> >> +(simplify

> >> + (bit_ior:c (bit_xor @0 @1) (bit_not:s (bit_ior @0 @1)))

> >> + (bit_not (bit_and @0 @1)))

> >

> > :cs on the bit_xor, :s on the second bit_ior

> >

> > Otherwise looks OK to me.

>

> --

> Marc Glisse
MCC CS Sept. 22, 2018, 7:14 a.m. | #9
Thanks a lot for the review, Richard!

- I have updated the patch.
- Had done a full "make check" with the
second draft.
- Did a "make check-gcc" with the final
patch.
- Both tests have the same tests
failing, that always fail:

g++.dg/pr80481.C
g++.dg/pr83239.C

Would be great if anyone willing
could push it to origin/trunk!

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 264170)
+++ gcc/match.pd	(working copy)
@@ -92,7 +92,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)
 (define_operator_list COND_TERNARY
   IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)
-    
+
 /* As opposed to convert?, this still creates a single pattern, so
    it is not a suitable replacement for convert? in all cases.  */
 (match (nop_convert @0)
@@ -106,7 +106,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
 /* This one has to be last, or it shadows the others.  */
 (match (nop_convert @0)
- @0) 
+ @0)
 
 /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
    ABSU_EXPR returns unsigned absolute value of the operand and the operand
@@ -285,7 +285,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      And not for _Fract types where we can't build 1.  */
   (if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))
    { build_one_cst (type); }))
- /* X / abs (X) is X < 0 ? -1 : 1.  */ 
+ /* X / abs (X) is X < 0 ? -1 : 1.  */
  (simplify
    (div:C @0 (abs @0))
    (if (INTEGRAL_TYPE_P (type)
@@ -921,6 +921,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (bitop:c @0 (bit_not (bitop:cs @0 @1)))
   (bitop @0 (bit_not @1))))
 
+/* (~x & y) | ~(x | y) -> ~x */
+(simplify
+ (bit_ior:c (bit_and:c (bit_not@2 @0) @1) (bit_not (bit_ior:c @0 @1)))
+ @2)
+
+/* (x | y) ^ (x | ~y) -> ~x */
+(simplify
+ (bit_xor:c (bit_ior:c @0 @1) (bit_ior:c @0 (bit_not @1)))
+ (bit_not @0))
+
+/* (x & y) | ~(x | y) -> ~(x ^ y) */
+(simplify
+ (bit_ior:c (bit_and:cs @0 @1) (bit_not:s (bit_ior:s @0 @1)))
+ (bit_not (bit_xor @0 @1)))
+
+/* (~x | y) ^ (x ^ y) -> x | ~y */
+(simplify
+ (bit_xor:c (bit_ior:cs (bit_not @0) @1) (bit_xor:s @0 @1))
+ (bit_ior @0 (bit_not @1)))
+
+/* (x ^ y) | ~(x | y) -> ~(x & y) */
+(simplify
+ (bit_ior:c (bit_xor:cs @0 @1) (bit_not:s (bit_ior:s @0 @1)))
+ (bit_not (bit_and @0 @1)))
+
 /* (x | y) & ~x -> y & ~x */
 /* (x & y) | ~x -> y | ~x */
 (for bitop (bit_and bit_ior)
@@ -1131,7 +1156,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
        && tree_nop_conversion_p (type, TREE_TYPE (@1)))
    (mult (convert @0) (convert (negate @1)))))
- 
+
 /* -(A + B) -> (-B) - A.  */
 (simplify
  (negate (plus:c @0 negate_expr_p@1))
@@ -3091,7 +3116,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (if (tree_int_cst_sgn (@1) < 0)
      (scmp @0 @2)
      (cmp @0 @2))))))
- 
+
 /* Simplify comparison of something with itself.  For IEEE
    floating-point, we can only do some of these simplifications.  */
 (for cmp (eq ge le)
@@ -3162,11 +3187,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
         }
       tree newtype
         = (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (type1)
-	   ? TREE_TYPE (@0) : type1); 
+	   ? TREE_TYPE (@0) : type1);
     }
     (if (TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (newtype))
      (cmp (convert:newtype @0) (convert:newtype @1))))))
- 
+
  (simplify
   (cmp @0 REAL_CST@1)
   /* IEEE doesn't distinguish +0 and -0 in comparisons.  */
@@ -3414,7 +3439,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	    (FTYPE) N == CST -> 0
 	    (FTYPE) N != CST -> 1.  */
 	(if (cmp == EQ_EXPR || cmp == NE_EXPR)
-	 { constant_boolean_node (cmp == NE_EXPR, type); }) 
+	 { constant_boolean_node (cmp == NE_EXPR, type); })
 	/* Otherwise replace with sensible integer constant.  */
 	(with
 	 {
@@ -3656,7 +3681,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (simplify
   (cmp (bit_and@2 @0 integer_pow2p@1) @1)
   (icmp @2 { build_zero_cst (TREE_TYPE (@0)); })))
- 
+
 /* If we have (A & C) != 0 ? D : 0 where C and D are powers of 2,
    convert this into a shift followed by ANDing with D.  */
 (simplify
@@ -3876,7 +3901,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
         (if (cmp == LE_EXPR)
 	 (ge (convert:st @0) { build_zero_cst (st); })
 	 (lt (convert:st @0) { build_zero_cst (st); }))))))))))
- 
+
 (for cmp (unordered ordered unlt unle ungt unge uneq ltgt)
  /* If the second operand is NaN, the result is constant.  */
  (simplify
@@ -4530,7 +4555,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (wi::to_wide (@1) == -1)
    (rdiv { build_real (type, dconst1); } @0))))
 
-/* Narrowing of arithmetic and logical operations. 
+/* Narrowing of arithmetic and logical operations.
 
    These are conceptually similar to the transformations performed for
    the C/C++ front-ends by shorten_binary_op and shorten_compare.  Long
@@ -4602,7 +4627,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      (convert (bit_and (op (convert:utype @0) (convert:utype @1))
 	       (convert:utype @4))))))))
 
-/* Transform (@0 < @1 and @0 < @2) to use min, 
+/* Transform (@0 < @1 and @0 < @2) to use min,
    (@0 > @1 and @0 > @2) to use max */
 (for logic (bit_and bit_and bit_and bit_and bit_ior bit_ior bit_ior bit_ior)
      op    (lt      le      gt      ge      lt      le      gt      ge     )
Index: gcc/testsuite/gcc.dg/pr87261.c
===================================================================
--- gcc/testsuite/gcc.dg/pr87261.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/pr87261.c	(working copy)
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-original" } */
+
+int f1 (int a, int b)
+{
+ return ~(a|b)|(~a&b);
+}
+
+int f2 (int a, int b)
+{
+ return (a|b)^(a|~b);
+}
+
+/* { dg-final { scan-tree-dump-times "return \\~a;" 2 "original" } } */
+
+int f3 (int a, int b)
+{
+ return ~(a|b)|(a&b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\^ b\\);" "original" } } */
+
+int f4 (int a, int b)
+{
+ return a^b^(~a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~b \\| a;" "original" } } */
+
+int f5 (int a, int b)
+{
+ return (a^b)|~(a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\& b\\);" "original" } } */

Patch

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 264170)
+++ gcc/match.pd	(working copy)
@@ -92,7 +92,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   IFN_FMA IFN_FMS IFN_FNMA IFN_FNMS)
 (define_operator_list COND_TERNARY
   IFN_COND_FMA IFN_COND_FMS IFN_COND_FNMA IFN_COND_FNMS)
-    
+
 /* As opposed to convert?, this still creates a single pattern, so
    it is not a suitable replacement for convert? in all cases.  */
 (match (nop_convert @0)
@@ -106,7 +106,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
 /* This one has to be last, or it shadows the others.  */
 (match (nop_convert @0)
- @0) 
+ @0)
 
 /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
    ABSU_EXPR returns unsigned absolute value of the operand and the operand
@@ -285,7 +285,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      And not for _Fract types where we can't build 1.  */
   (if (!integer_zerop (@0) && !ALL_FRACT_MODE_P (TYPE_MODE (type)))
    { build_one_cst (type); }))
- /* X / abs (X) is X < 0 ? -1 : 1.  */ 
+ /* X / abs (X) is X < 0 ? -1 : 1.  */
  (simplify
    (div:C @0 (abs @0))
    (if (INTEGRAL_TYPE_P (type)
@@ -921,6 +921,31 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (bitop:c @0 (bit_not (bitop:cs @0 @1)))
   (bitop @0 (bit_not @1))))
 
+/* (~x & y) | ~(x | y) -> ~x */
+(simplify
+ (bit_ior:c (bit_and:c (bit_not @0) @1) (bit_not (bit_ior:s @0 @1)))
+ (bit_not @0))
+
+/* (x | y) ^ (x | ~y) -> ~x */
+(simplify
+ (bit_xor:c (bit_ior:s @0 @1) (bit_ior:c @0 (bit_not @1)))
+ (bit_not @0))
+
+/* (x & y) | ~(x | y) -> ~(x ^ y) */
+(simplify
+ (bit_ior:c (bit_and:s @0 @1) (bit_not (bit_ior:s @0 @1)))
+ (bit_not (bit_xor @0 @1)))
+
+/* (~x | y) ^ (x ^ y) -> x | ~y */
+(simplify
+ (bit_xor:c (bit_ior:c (bit_not @0) @1) (bit_xor:s @0 @1))
+ (bit_ior @0 (bit_not @1)))
+
+/* (x ^ y) | ~(x | y) -> ~(x & y) */
+(simplify
+ (bit_ior:c (bit_xor:s @0 @1) (bit_not (bit_ior:s @0 @1)))
+ (bit_not (bit_and @0 @1)))
+
 /* (x | y) & ~x -> y & ~x */
 /* (x & y) | ~x -> y | ~x */
 (for bitop (bit_and bit_ior)
@@ -1131,7 +1156,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
        && tree_nop_conversion_p (type, TREE_TYPE (@1)))
    (mult (convert @0) (convert (negate @1)))))
- 
+
 /* -(A + B) -> (-B) - A.  */
 (simplify
  (negate (plus:c @0 negate_expr_p@1))
@@ -3091,7 +3116,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (if (tree_int_cst_sgn (@1) < 0)
      (scmp @0 @2)
      (cmp @0 @2))))))
- 
+
 /* Simplify comparison of something with itself.  For IEEE
    floating-point, we can only do some of these simplifications.  */
 (for cmp (eq ge le)
@@ -3162,11 +3187,11 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
         }
       tree newtype
         = (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (type1)
-	   ? TREE_TYPE (@0) : type1); 
+	   ? TREE_TYPE (@0) : type1);
     }
     (if (TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (newtype))
      (cmp (convert:newtype @0) (convert:newtype @1))))))
- 
+
  (simplify
   (cmp @0 REAL_CST@1)
   /* IEEE doesn't distinguish +0 and -0 in comparisons.  */
@@ -3414,7 +3439,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	    (FTYPE) N == CST -> 0
 	    (FTYPE) N != CST -> 1.  */
 	(if (cmp == EQ_EXPR || cmp == NE_EXPR)
-	 { constant_boolean_node (cmp == NE_EXPR, type); }) 
+	 { constant_boolean_node (cmp == NE_EXPR, type); })
 	/* Otherwise replace with sensible integer constant.  */
 	(with
 	 {
@@ -3656,7 +3681,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (simplify
   (cmp (bit_and@2 @0 integer_pow2p@1) @1)
   (icmp @2 { build_zero_cst (TREE_TYPE (@0)); })))
- 
+
 /* If we have (A & C) != 0 ? D : 0 where C and D are powers of 2,
    convert this into a shift followed by ANDing with D.  */
 (simplify
@@ -3876,7 +3901,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
         (if (cmp == LE_EXPR)
 	 (ge (convert:st @0) { build_zero_cst (st); })
 	 (lt (convert:st @0) { build_zero_cst (st); }))))))))))
- 
+
 (for cmp (unordered ordered unlt unle ungt unge uneq ltgt)
  /* If the second operand is NaN, the result is constant.  */
  (simplify
@@ -4530,7 +4555,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (wi::to_wide (@1) == -1)
    (rdiv { build_real (type, dconst1); } @0))))
 
-/* Narrowing of arithmetic and logical operations. 
+/* Narrowing of arithmetic and logical operations.
 
    These are conceptually similar to the transformations performed for
    the C/C++ front-ends by shorten_binary_op and shorten_compare.  Long
@@ -4602,7 +4627,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      (convert (bit_and (op (convert:utype @0) (convert:utype @1))
 	       (convert:utype @4))))))))
 
-/* Transform (@0 < @1 and @0 < @2) to use min, 
+/* Transform (@0 < @1 and @0 < @2) to use min,
    (@0 > @1 and @0 > @2) to use max */
 (for logic (bit_and bit_and bit_and bit_and bit_ior bit_ior bit_ior bit_ior)
      op    (lt      le      gt      ge      lt      le      gt      ge     )
Index: gcc/testsuite/gcc.dg/pr87261.c
===================================================================
--- gcc/testsuite/gcc.dg/pr87261.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/pr87261.c	(working copy)
@@ -0,0 +1,35 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-original" } */
+
+int f1 (int a, int b)
+{
+ return ~(a|b)|(~a&b);
+}
+
+int f2 (int a, int b)
+{
+ return (a|b)^(a|~b);
+}
+
+/* { dg-final { scan-tree-dump-times "return \\~a;" 2 "original" } } */
+
+int f3 (int a, int b)
+{
+ return ~(a|b)|(a&b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\^ b\\);" "original" } } */
+
+int f4 (int a, int b)
+{
+ return a^b^(~a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~b \\| a;" "original" } } */
+
+int f5 (int a, int b)
+{
+ return (a^b)|~(a|b);
+}
+
+/* { dg-final { scan-tree-dump "return \\~\\(a \\& b\\);" "original" } } */