Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns

[Richard Guenther <richard dot guenther at gmail dot com>]

On Fri, Jul 1, 2011 at 5:23 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> So updated patch (bootstrapped and tested for all standard languages
> plus Ada and Obj-C++) on x86_64-pc-linux-gnu host.
>
> Index: gcc-head/gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc-head.orig/gcc/tree-ssa-forwprop.c
> +++ gcc-head/gcc/tree-ssa-forwprop.c
> @@ -1602,6 +1602,156 @@ simplify_builtin_call (gimple_stmt_itera
> ? return false;
> ?}
>
> +/* Checks if expression has type of one-bit precision, or is a known
> + ? truth-valued expression. ?*/
> +static bool
> +truth_valued_ssa_name (tree name)
> +{
> + ?gimple def;
> + ?tree type = TREE_TYPE (name);
> +
> + ?if (!INTEGRAL_TYPE_P (type))
> + ? ?return false;
> + ?/* Don't check here for BOOLEAN_TYPE as the precision isn't
> + ? ? necessarily one and so ~X is not equal to !X. ?*/
> + ?if (TYPE_PRECISION (type) == 1)
> + ? ?return true;
> + ?def = SSA_NAME_DEF_STMT (name);
> + ?if (is_gimple_assign (def))
> + ? ?return truth_value_p (gimple_assign_rhs_code (def));
> + ?return false;
> +}
> +
> +/* Helper routine for simplify_bitwise_binary_1 function.
> + ? Return for the SSA name NAME the expression X if it mets condition
> + ? NAME = !X. Otherwise return NULL_TREE.
> + ? Detected patterns for NAME = !X are:
> + ? ? !X and X == 0 for X with integral type.
> + ? ? X ^ 1, X != 1,or ~X for X with integral type with precision of one. ?*/
> +static tree
> +lookup_logical_inverted_value (tree name)
> +{
> + ?tree op1, op2;
> + ?enum tree_code code;
> + ?gimple def;
> +
> + ?/* If name has none-intergal type, or isn't a SSA_NAME, then
> + ? ? return. ?*/
> + ?if (TREE_CODE (name) != SSA_NAME
> + ? ? ?|| !INTEGRAL_TYPE_P (TREE_TYPE (name)))
> + ? ?return NULL_TREE;
> + ?def = SSA_NAME_DEF_STMT (name);
> + ?if (!is_gimple_assign (def))
> + ? ?return NULL_TREE;
> +
> + ?code = gimple_assign_rhs_code (def);
> + ?op1 = gimple_assign_rhs1 (def);
> + ?op2 = NULL_TREE;
> +
> + ?/* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
> + ? ? If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR,
> + ? ? or BIT_NOT_EXPR, then return. ?*/
> + ?if (code == EQ_EXPR || code == NE_EXPR
> + ? ? ?|| code == BIT_XOR_EXPR)
> + ? ?op2 = gimple_assign_rhs2 (def);
> +
> + ?switch (code)
> + ? ?{
> + ? ?case TRUTH_NOT_EXPR:
> + ? ? ?return op1;
> + ? ?case BIT_NOT_EXPR:
> + ? ? ?if (truth_valued_ssa_name (name))
> + ? ? ? return op1;
> + ? ? ?break;
> + ? ?case EQ_EXPR:
> + ? ? ?/* Check if we have X == 0 and X has an integral type. ?*/
> + ? ? ?if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
> + ? ? ? break;
> + ? ? ?if (integer_zerop (op2))
> + ? ? ? return op1;
> + ? ? ?break;
> + ? ?case NE_EXPR:
> + ? ? ?/* Check if we have X != 1 and X is a truth-valued. ?*/
> + ? ? ?if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
> + ? ? ? break;
> + ? ? ?if (integer_onep (op2) && truth_valued_ssa_name (op1))
> + ? ? ? return op1;
> + ? ? ?break;
> + ? ?case BIT_XOR_EXPR:
> + ? ? ?/* Check if we have X ^ 1 and X is truth valued. ?*/
> + ? ? ?if (integer_onep (op2) && truth_valued_ssa_name (op1))
> + ? ? ? return op1;
> + ? ? ?break;
> + ? ?default:
> + ? ? ?break;
> + ? ?}
> +
> + ?return NULL_TREE;
> +}
> +
> +/* Try to optimize patterns X & !X -> zero, X | !X -> one, and
> + ? X ^ !X -> one, if type of X is valid for this.
> +
> + ? See for list of detected logical-not patterns the
> + ? lookup_logical_inverted_value function. ?*/

As usual - refer to actual arguments.  I'd do

/* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
   operations CODE if one operand has the logically inverted
   value of the other.  */

> +static tree
> +simplify_bitwise_binary_1 (enum tree_code code, tree arg1,
> + ? ? ? ? ? ? ? ? ? ? ? ? ?tree arg2)
> +{
> + ?tree a1not, a2not;
> + ?tree op = NULL_TREE;
> +
> + ?/* If CODE isn't a bitwise binary operation, return NULL_TREE. ?*/
> + ?if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
> + ? ? ?&& code != BIT_XOR_EXPR)
> + ? ?return NULL_TREE;
> +
> + ?/* First check if operands ARG1 and ARG2 are equal. ?*/
> + ?if (operand_equal_p (arg1, arg2, 0))
> + ? ?return NULL_TREE;

That's an early out - use arg1 == arg2 instead and mention why
we do not optimize it - it's done by fold_stmt.

> + ?/* See if we have in arguments logical-not patterns. ?*/
> + ?a1not = lookup_logical_inverted_value (arg1);
> + ?a2not = lookup_logical_inverted_value (arg2);

You didn't re-organize the code to only call one of the lookups if
that succeeded as I requested.

> + ?/* If there are no logical-not in arguments, ?return NULL_TREE. */
> + ?if (!a1not && !a2not)
> + ? ?return NULL_TREE;
> +
> + ?/* If both arguments are logical-not patterns, then try to fold
> + ? ? them or return NULL_TREE. ?*/
> + ?if (a1not && a2not)
> + ? ?{
> + ? ? ?/* If logical-not operands of ARG1 and ARG2 are equal, then fold
> + ? ? ? ?them.. ?*/

No double-full-stop please.  Instead of "fold" say "simplify".

> + ? ? ?if (operand_equal_p (a1not, a2not, 0))

The only case where a1not or a2not are not SSA names are when they
are constants (missed optimization anyway) or when they are
invariant addresses (not INTEGRAL_TYPE_P).  So just sue a1not == a2not
instead of operand_equal_p.

Also if you are handling !X OP !X here then this sounds fishy (as I said
already ...), CSE should make sure that !X and !X are redundant.  If that
doesn't work for a testcase then please file a bugreport.  We shouldn't
repeatedly handle cases that should not happen - that just makes code
bigger, less maintainable (confusing to the casual reader) and slower.

> + ? ? ? {
> + ? ? ? ? /* !X & !X -> !X, and !X | !X -> !X. ?*/
> + ? ? ? ? if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
> + ? ? ? ? ? return arg1;
> + ? ? ? ? /* !X ^ !X -> 0. ?*/
> + ? ? ? ? return integer_zero_node;
> + ? ? ? }
> + ? ? ?return NULL_TREE;
> + ? ?}
> +
> + ?if (a2not && operand_equal_p (arg1, a2not, 0))

See above.

> + ? ?op = arg1;
> + ?else if (a1not && operand_equal_p (arg2, a1not, 0))

Likewise.

> + ? ?op = arg2;
> + ?else
> + ? ?return NULL_TREE;
> +
> + ?/* X & !X -> 0. ?*/
> + ?if (code == BIT_AND_EXPR)
> + ? ?return integer_zero_node;

Instead of returning integer_*_node please pass down the desired
result type and return a properly typed constant.  That'll simplify
the caller code.

> + ?/* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. ?*/
> + ?if (truth_valued_ssa_name (op))
> + ? ?return integer_one_node;
> +
> + ?/* ??? Otherwise result is (X != 0 ? X : 1. ?not handled. ?*/

Missing closing paren.  Also I think the comment is about sth we
do not want to handle anyway.

> + ?return NULL_TREE;
> +}
> +
> ?/* Simplify bitwise binary operations.
> ? ?Return true if a transformation applied, otherwise return false. ?*/
>
> @@ -1768,7 +1918,31 @@ simplify_bitwise_binary (gimple_stmt_ite
> ? ? ? update_stmt (stmt);
> ? ? ? return true;
> ? ? }

Insert vertical space.

> + ?/* Try simple folding for X op !X, and X op X. ?*/
> + ?res = simplify_bitwise_binary_1 (code, arg1, arg2);
> + ?if (res != NULL_TREE && TREE_CODE (res) == INTEGER_CST)
> + ? ?{
> + ? ? ?res = fold_convert_loc (gimple_location (stmt),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? TREE_TYPE (arg1), res);
> + ? ? ?gimple_assign_set_rhs_from_tree (gsi, res);
> + ? ? ?update_stmt (gsi_stmt (*gsi));
> + ? ? ?return true;
> + ? ?}
> + ?else if (res)
> + ? ?{
> + ? ? ?if (!useless_type_conversion_p (TREE_TYPE (arg1), TREE_TYPE (res)))

No need to separate out the constant case.  When would we ever
return mismatching types?  Never!  So please simplify this.

Richard.

> + ? ? ? {
> + ? ? ? ? res = force_gimple_operand_gsi (gsi, res, true, NULL_TREE, true,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? GSI_SAME_STMT);
>
> + ? ? ? ? gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? res, NULL_TREE, NULL_TREE);
> + ? ? ? }
> + ? ? ?else
> + ? ? ? gimple_assign_set_rhs_from_tree (gsi, res);
> + ? ? ?update_stmt (gsi_stmt (*gsi));
> + ? ? ?return true;
> + ? ?}
> ? return false;
> ?}
>
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (char a, unsigned short b)
> +{
> + ?return (a & !a) | (b & !b);
> +}
> +
> +/* As long as comparisons aren't boolified and casts from boolean-types
> + ? aren't preserved, the folding of ?X & !X to zero fails. ?*/
> +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail
> *-*-* } } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (int a)
> +{
> + ?return (!a & 1) != (a == 0);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (short a)
> +{
> + ?return (!a & 1) != ((a == 0) & 1);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (unsigned char a, _Bool b)
> +{
> + ?return (!a & a) | (b & !b);
> +}
> +
> +/* As long as comparisons aren't boolified and casts from boolean-types
> + ? aren't preserved, the folding of ?X & !X to zero fails. ?*/
> +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail
> *-*-* } } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (long a, unsigned long b)
> +{
> + ?return (a & (a == 0)) | (b & !b);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (unsigned long a, long b)
> +{
> + ?return (a & !a) | (b & (b == 0));
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (_Bool a, _Bool b)
> +{
> + ?return (a | !a) | (!b | b);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (_Bool a, _Bool b)
> +{
> + ?return (a | (a == 0)) | ((b ^ 1) | b);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (_Bool a, _Bool b)
> +{
> + ?return (a ^ !a) | (!b ^ b);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (_Bool a, _Bool b)
> +{
> + ?return (a ^ (a == 0)) | ((b == 0) ^ b);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>