----- Original Message -----
From: "Richard Guenther" <[email protected]>
To: "Kai Tietz" <[email protected]>
Cc: [email protected]
Sent: Thursday, June 30, 2011 1:36:13 PM
Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X
op !X patterns
On Wed, Jun 29, 2011 at 3:00 PM, Kai Tietz <[email protected]> wrote:
> ----- Original Message -----
> From: "Kai Tietz" <[email protected]>
> To: "Richard Guenther" <[email protected]>
> Cc: [email protected]
> Sent: Wednesday, June 29, 2011 1:33:30 PM
> Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for
> X op !X patterns
>
> ----- Original Message -----
> From: "Richard Guenther" <[email protected]>
> To: "Kai Tietz" <[email protected]>
> Cc: [email protected]
> Sent: Wednesday, June 29, 2011 12:14:10 PM
> Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for
> X op !X patterns
>
> On Tue, Jun 28, 2011 at 5:05 PM, Kai Tietz <[email protected]> wrote:
>> Hello,
>>
>> this patch implements the X op !X patterns within tree-ssa-forwprop.c
>> without using here const-fold routines. Additionally it does some trivial
>> folding for X op X. Implementation
>> also looks through [(type)] X op [(type)] !X, if type of X is integral and
>> precision is suitable
>> for operation.
>>
>> ChangeLog gcc/
>>
>> 2011-06-28 Kai Tietz <[email protected]>
>>
>> * tree-ssa-forwprop.c (operand_precision_onep): New
>> function.
>> (find_possible_not_expr_argument): Likewise.
>> (simplify_bitwise_binary_1): Likewise.
>> (simplify_bitwise_binary): Use simplify_bitwise_binary_1
>> for detecting various X op !X optimizations.
>>
>> ChangeLog gcc/testsuite
>>
>> 2011-06-28 Kai Tietz <[email protected]>
>>
>> * gcc.dg/binop-notand1a.c: New test.
>> * gcc.dg/binop-notand2a.c: New test.
>> * gcc.dg/binop-notand3a.c: New test.
>> * gcc.dg/binop-notand4a.c: New test.
>> * gcc.dg/binop-notand5a.c: New test.
>> * gcc.dg/binop-notand6a.c: New test.
>> * gcc.dg/binop-notor1.c: New test.
>> * gcc.dg/binop-notor2.c: New test.
>> * gcc.dg/binop-notxor1.c: New test.
>> * gcc.dg/binop-notxor2.c: New test.
>>
>> Bootstrapped and regression tested for all languages plus Ada and Obj-C for
>> x86_64-pc-linux-gnu. Ok for apply?
>
> I can't follow the code in find_possible_not_expr_argument or its uses
> at all. Please try to produce patches that look more obvious in what
> they are doing - don't try to solve every testcase you can come up with
> in a single patch. Especially don't write functions like
> find_possible_not_expr_argument which seems to have evolved a lot
> after you wrote the overall function comment.
>
> Thanks,
> Richard.
>
>> Regards,
>> Kai
>>
>
> Well, I added some comments to these functions and renamed the
> find_possible_not_expr_argument function to detect_not_expr_operand, which
> hits its use better.
> The cause for this function is, that there are more then one variant of
> expressing a logical-not and all of them are used.
> This routine simply tries to detect different variants used for not. Eg ~X ==
> !X and (X ^ 1) == !X for integral type of X with precision one. For X with
> integral type, (X == 0) == !X.
>
> The folding for the three different bitwise-operations is pretty easy and it
> makes sense to implement them at once. I see here no good point to separate
> them into different patches. To separate them might even lead to questions
> about abstracting some code-pieces out of the main function.
> I didn't added testcases for all variants I am aware now. Just those, which
> are now handled.
>
> So hope you can read and understand logic of patch better by updated patch.
>
> Regards,
> Kai
>
> I found that in version I've sent there is an unclosed comment. So here is
> updated patch, which additionally simplify some code to ease reading.
Ok, I'm going to comment on a few things in the patch.
+/* Checks if expression has type of one-bit precision, or is result of
+ a known boolean expression. */
+static bool
+operand_precision_onep (tree expr)
+{
+ enum tree_code code;
+ gimple def_stmt;
+
+ do
+ {
+ code = TREE_CODE (expr);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (expr)))
+ return false;
+ if (TYPE_PRECISION (TREE_TYPE (expr)) == 1)
+ return true;
+ if (code != SSA_NAME)
+ break;
+ def_stmt = SSA_NAME_DEF_STMT (expr);
+ if (!def_stmt || !is_gimple_assign (def_stmt))
+ break;
+ code = gimple_assign_rhs_code (def_stmt);
+ if (!CONVERT_EXPR_CODE_P (code))
+ break;
+ expr = gimple_assign_rhs1 (def_stmt);
+ }
+ while (CONVERT_EXPR_CODE_P (code));
+
+ if (code == TRUTH_NOT_EXPR || TREE_CODE_CLASS (code) == tcc_comparison)
+ return true;
+ return false;
+}
Please don't do arbitrary deep lookups like this. Instead this
function should be
bool
truth_valued_ssa_name_p (tree name)
{
tree type = TREE_TYPE (name);
gimple def_stmt;
if (!INTEGRAL_TYPE_P (type))
return false;
if (TREE_CODE (type) == BOOLEAN_TYPE
|| TYPE_PRECISION (type) == 1)
return true;
def_stmt = SSA_NAME_DEF_STMT (name);
if (is_gimple_assign (def_stmt))
return truth_value_p (gimple_assign_rhs_code (def_stmt));
return false;
}
+static tree
+detect_not_expr_operand (tree name, tree *nexpr)
same, don't do arbitrary deep lookups. Do simple matches by
enumerating them. The code is not followable or easily verifiable
for correctness. Look at how all the code in fold-const.c is written - it's
very easy to follow what is matched and what is produced. This is not
at all the case for your code.
Richard.
> Regards,
> Kai
>
Ok, here is reworked patch with adjusted testcase.
ChangeLog gcc/
2011-07-01 Kai Tietz <[email protected]>
* tree-ssa-forwprop.c (truth_valued_ssa): New function.
(detect_not_expr_operand): New function.
(simplify_bitwise_binary_1): New function.
(simplify_bitwise_binary): Use simplify_bitwise_binary_1.
ChangeLog gcc/
2011-07-01 Kai Tietz <[email protected]>
* gcc.dg/binop-notand1a.c: New test.
* gcc.dg/binop-notand2a.c: New test.
* gcc.dg/binop-notand3a.c: New test.
* gcc.dg/binop-notand4a.c: New test.
* gcc.dg/binop-notand5a.c: New test.
* gcc.dg/binop-notand6a.c: New test.
* gcc.dg/binop-notor1.c: New test.
* gcc.dg/binop-notor2.c: New test.
* gcc.dg/binop-notxor1.c: New test.
* gcc.dg/binop-notxor2.c: New test.
Bootstrapped and regression tested for all standard languages plus Ada and
Obj-C++ for x86_64-pc-linux-gnu. Ok for apply?
Regards,
Kai
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,179 @@ simplify_builtin_call (gimple_stmt_itera
return false;
}
+/* Checks if expression has type of one-bit precision, or is a known
+ truth-value pression. */
+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.
+ If a NOT-expression is found, the operand of the NOT-expression is
+ returned. Othewise NULL_TREE is returned.
+ Detected not-patterns are !X or X == 0 for X with integral type, and
+ X ^ 1 or ~X for X with integral type with precision of one.
+ The value of CNT_CASTS is either zero, or one. */
+static tree
+detect_not_expr_operand (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 (!def || !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 == 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;
+ else if (integer_zerop (op1))
+ return op2;
+ 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 & not(X) -> zero, X | not(X) -> one, and
+ X ^ not(X) -> one, if type of X is valid for this.
+ Additional handle the variants X & X -> X, X | X -> X, and X ^ X -> zero.
+
+ See for detected not-patterns the detect_not_expr_operand function. */
+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 so we
+ won't have a NOT-pattern match. Fold these patterns, as
+ we have detected it already. */
+ if (operand_equal_p (arg1, arg2, 0))
+ {
+ /* 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;
+ }
+ /* Get for each operation operand its optional by one integral typed
+ cast stripped argument. And get the not-expression's operand, if
+ argument represents an not-expression. */
+ a1not = detect_not_expr_operand (arg1);
+ a2not = detect_not_expr_operand (arg2);
+
+ /* If there are no not-expressions found, return NULL_TREE. */
+ if (!a1not && !a2not)
+ return NULL_TREE;
+
+ /* Do we have case not(X) op not(X)? */
+ if (a1not && a2not)
+ {
+ /* Check if operands not(ARG1) and not(ARG2) are equal and
+ fold them if so. */
+ if (operand_equal_p (a1not, a2not, 0))
+ {
+ /* !X & !X -> !X, and !X | i!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)
+ {
+ /* X equal to Y for X op not(Y) */
+ if (operand_equal_p (arg1, a2not, 0))
+ op = arg1;
+ }
+ if (!op && a1not)
+ {
+ /* X equal to Y for not(X) op Y */
+ if (operand_equal_p (arg2, a1not, 0))
+ op = arg2;
+ }
+ /* No match, return NULL_TREE. */
+ if (!op)
+ return NULL_TREE;
+
+ /* X & not(X) -> 0. */
+ if (code == BIT_AND_EXPR)
+ return integer_zero_node;
+ else if (code == BIT_IOR_EXPR)
+ {
+ /* X | not(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. */
+ }
+ else if (code == BIT_XOR_EXPR)
+ {
+ /* X ^ not(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. */
+ }
+ return NULL_TREE;
+}
+
/* Simplify bitwise binary operations.
Return true if a transformation applied, otherwise return false. */
@@ -1768,7 +1941,31 @@ simplify_bitwise_binary (gimple_stmt_ite
update_stmt (stmt);
return true;
}
+ /* 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)))
+ {
+ 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" } } */
