* [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns [not found] <196308741.816832.1309273513615.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com> @ 2011-06-28 15:40 ` Kai Tietz 2011-06-29 11:28 ` Richard Guenther 0 siblings, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-06-28 15:40 UTC (permalink / raw) To: gcc-patches; +Cc: Richard Guenther [-- Attachment #1: Type: text/plain, Size: 1298 bytes --] 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 <ktietz@redhat.com> * 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 <ktietz@redhat.com> * 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? Regards, Kai [-- Attachment #2: fold_fw.txt --] [-- Type: text/plain, Size: 11510 bytes --] Index: gcc-head/gcc/tree-ssa-forwprop.c =================================================================== --- gcc-head.orig/gcc/tree-ssa-forwprop.c +++ gcc-head/gcc/tree-ssa-forwprop.c @@ -1674,6 +1674,189 @@ simplify_builtin_call (gimple_stmt_itera return false; } +/* 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; + + 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) + { + gimple 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); + } + else + break; + } + while (CONVERT_EXPR_CODE_P (code)); + if (code == TRUTH_NOT_EXPR || TREE_CODE_CLASS (code) == tcc_comparison) + return true; + return false; +} + +/* Helper routine for simplify_bitwise_binary_1 for counting + ignored type casts in CNT_CASTS, and finding possible match + returned in NEXPR. This function returns the first expression + not being a cast. */ +static tree +find_possible_not_expr_argument (tree name, int *cnt_casts, tree *nexpr) +{ + enum tree_code code = ERROR_MARK; + *cnt_casts = 0; + *nexpr = NULL_TREE; + + while (1) + { + tree op1, op2; + gimple def_stmt; + code = TREE_CODE (name); + /* If name has none-intergal type, or isn't a SSA_NAME, then + stop search. */ + if (code != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (name))) + break; + def_stmt = SSA_NAME_DEF_STMT (name); + if (!def_stmt || !is_gimple_assign (def_stmt)) + break; + code = gimple_assign_rhs_code (def_stmt); + op1 = gimple_assign_rhs1 (def_stmt); + op2 = NULL_TREE; + if (code == EQ_EXPR || code == BIT_XOR_EXPR) + op2 = gimple_assign_rhs2 (def_stmt); + else if (!CONVERT_EXPR_CODE_P (code) + && code != TRUTH_NOT_EXPR) + break; + if (code == TRUTH_NOT_EXPR + || (code == BIT_NOT_EXPR + && INTEGRAL_TYPE_P (name) + && operand_precision_onep (name))) + { + *nexpr = op1; + break; + } + else if (code == EQ_EXPR || code == BIT_XOR_EXPR) + { + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) + break; + if (code == EQ_EXPR + && TREE_CODE (op2) == INTEGER_CST + && integer_zerop (op2)) + *nexpr = op1; + else if (code == EQ_EXPR + && TREE_CODE (op1) == INTEGER_CST + && integer_zerop (op1)) + *nexpr = op2; + else if (code == BIT_XOR_EXPR + && operand_precision_onep (op1) + && TREE_CODE (op2) == INTEGER_CST + && integer_onep (op2)) + *nexpr = op1; + else if (code == BIT_XOR_EXPR + && operand_precision_onep (op2) + && TREE_CODE (op1) == INTEGER_CST + && integer_onep (op1)) + *nexpr = op2; + break; + } + else if (!CONVERT_EXPR_CODE_P (code)) + break; + /* Just allow sinking over one cast and this only for + integeral types. Otherwise value truncation + or intermediate float conversions need to be + considered. */ + if (cnt_casts[0] != 0) + break; + cnt_casts[0] += 1; + name = op1; + } + return name; +} + +/* Try to optimize patterns X & !X -> zero, X | !X -> one, and X ^ !X -> one, + if type of X allows this. Additional handle the variants X & X -> X, + X | X -> X, and X ^ X -> zero. + For integral type-casts we also pattern match (type) X op !X, + (type) X op (type) !X, and X op (type) !X sub-variants. */ +static tree +simplify_bitwise_binary_1 (enum tree_code code, tree arg1, tree arg2) +{ + int a1cnt = 0, a2cnt = 0; + tree a1strip, a1expr; + tree a2strip, a2expr; + tree op = NULL_TREE; + + if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR + && code != BIT_XOR_EXPR) + return NULL_TREE; + + if (operand_equal_p (arg1, arg2, 0)) + { + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + return integer_zero_node; + } + a1strip = find_possible_not_expr_argument (arg1, &a1cnt, &a1expr); + a2strip = find_possible_not_expr_argument (arg2, &a2cnt, &a2expr); + + if (a1cnt == a2cnt && operand_equal_p (a1strip, a2strip, 0)) + { + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + return integer_zero_node; + } + + if (!a1expr && !a2expr) + return NULL_TREE; + + if (a2expr) + { + if (operand_equal_p (arg1, a2expr, 0) + || operand_equal_p (a1strip, a2expr, 0)) + op = arg1; + } + if (!op && a1expr) + { + if (operand_equal_p (arg2, a1expr, 0) + || operand_equal_p (a2strip, a1expr, 0)) + op = arg2; + } + if (!op) + return NULL_TREE; + + /* We have found a X op !X operation. */ + if (code == BIT_AND_EXPR) + return integer_zero_node; + else if (code == BIT_IOR_EXPR) + { + /* If X has type precision of one, then result is 1. */ + if ((op == arg1 && operand_precision_onep (a1strip)) + || (op == arg2 && operand_precision_onep (a2strip))) + return integer_one_node; + /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ + } + else + { + /* Result for XOR for X with type precision of one is 1. */ + if ((op == arg1 && operand_precision_onep (a1strip)) + || (op == arg2 && operand_precision_onep (a2strip))) + 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. */ @@ -1862,7 +2045,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,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (char a, unsigned short b) +{ + return (a & !a) | (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-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,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned char a, _Bool b) +{ + return (!a & a) | (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-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" } } */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-06-28 15:40 ` [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns Kai Tietz @ 2011-06-29 11:28 ` Richard Guenther 2011-06-29 12:52 ` Kai Tietz 0 siblings, 1 reply; 14+ messages in thread From: Richard Guenther @ 2011-06-29 11:28 UTC (permalink / raw) To: Kai Tietz; +Cc: gcc-patches On Tue, Jun 28, 2011 at 5:05 PM, Kai Tietz <ktietz@redhat.com> 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 <ktietz@redhat.com> > > * 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 <ktietz@redhat.com> > > * 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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-06-29 11:28 ` Richard Guenther @ 2011-06-29 12:52 ` Kai Tietz 2011-06-29 13:41 ` Kai Tietz 0 siblings, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-06-29 12:52 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 3184 bytes --] ----- Original Message ----- From: "Richard Guenther" <richard.guenther@gmail.com> To: "Kai Tietz" <ktietz@redhat.com> Cc: gcc-patches@gcc.gnu.org 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 <ktietz@redhat.com> 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 <ktietz@redhat.com> > > * 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 <ktietz@redhat.com> > > * 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 [-- Attachment #2: fold_fw.txt --] [-- Type: text/plain, Size: 13298 bytes --] Index: gcc-head/gcc/tree-ssa-forwprop.c =================================================================== --- gcc-head.orig/gcc/tree-ssa-forwprop.c +++ gcc-head/gcc/tree-ssa-forwprop.c @@ -1674,6 +1674,228 @@ simplify_builtin_call (gimple_stmt_itera return false; } +/* 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; + + 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) + { + gimple 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); + } + else + break; + } + while (CONVERT_EXPR_CODE_P (code)); + if (code == TRUTH_NOT_EXPR || TREE_CODE_CLASS (code) == tcc_comparison) + return true; + return false; +} + +/* Helper routine for simplify_bitwise_binary_1 function. + Ignored integral type cast is counted in CNT_CASTS. If a not expression + is found, the operand of the not-expression is stored in NEXPR. + This function returns the either the expression after the first + integral cast expression, or NAME. + 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, int *cnt_casts, tree *nexpr) +{ + enum tree_code code = ERROR_MARK; + *cnt_casts = 0; + *nexpr = NULL_TREE; + + while (1) + { + tree op1, op2; + gimple def_stmt; + code = TREE_CODE (name); + /* If name has none-intergal type, or isn't a SSA_NAME, then + stop search. */ + if (code != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (name))) + break; + def_stmt = SSA_NAME_DEF_STMT (name); + if (!def_stmt || !is_gimple_assign (def_stmt)) + break; + + code = gimple_assign_rhs_code (def_stmt); + op1 = gimple_assign_rhs1 (def_stmt); + 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, + BIT_NOT_EXPR, and no conversion, break search. */ + if (code == EQ_EXPR || code == BIT_XOR_EXPR) + op2 = gimple_assign_rhs2 (def_stmt); + else if (!CONVERT_EXPR_CODE_P (code) + && code != TRUTH_NOT_EXPR + && code != BIT_NOT_EXPR) + break; + /* If !X or ~X is found, set NEXPR and break search. */ + if (code == TRUTH_NOT_EXPR + || (code == BIT_NOT_EXPR + && INTEGRAL_TYPE_P (name) + && operand_precision_onep (name))) + { + *nexpr = op1; + break; + } + /* If X == 0 or X ^ 1 is found, set NEXPR and break search. */ + else if (code == EQ_EXPR || code == BIT_XOR_EXPR) + { + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) + break; + if (code == EQ_EXPR + && TREE_CODE (op2) == INTEGER_CST + && integer_zerop (op2)) + *nexpr = op1; + else if (code == EQ_EXPR + && TREE_CODE (op1) == INTEGER_CST + && integer_zerop (op1)) + *nexpr = op2; + else if (code == BIT_XOR_EXPR + && operand_precision_onep (op1) + && TREE_CODE (op2) == INTEGER_CST + && integer_onep (op2)) + *nexpr = op1; + else if (code == BIT_XOR_EXPR + && operand_precision_onep (op2) + && TREE_CODE (op1) == INTEGER_CST + && integer_onep (op1)) + *nexpr = op2; + break; + } + /* If expression isn't a conversion, break search. */ + else if (!CONVERT_EXPR_CODE_P (code)) + break; + /* Just allow sinking over one cast and this only for + integeral types. Otherwise value truncation + or intermediate float conversions need to be + considered. */ + if (cnt_casts[0] != 0) + break; + cnt_casts[0] += 1; + name = op1; + } + + return name; +} + +/* 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. + We also pattern match optional integral type casts on operation's + operands. + + 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) +{ + int a1cnt = 0, a2cnt = 0; + tree a1strip, a1expr; + tree a2strip, a2expr; + 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. */ + a1strip = detect_not_expr_operand (arg1, &a1cnt, &a1expr); + a2strip = detect_not_expr_operand (arg2, &a2cnt, &a2expr); + + /* If there are no not-expressions found, return NULL_TREE. */ + if (!a1expr && !a2expr) + return NULL_TREE; + + /* Do we have case not(X) op not(X)? */ + if (a1expr && a2expr) + { + /* Check if operands not(ARG1) and not(ARG2) are equal and + fold them if so. + if (operand_equal_p (a1expr, a2expr, 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 (a2expr) + { + /* Check if X is equal for cases X CODE not(X), or + (type) X not(X). */ + if (operand_equal_p (arg1, a2expr, 0) + || operand_equal_p (a1strip, a2expr, 0)) + op = arg1; + } + /* If haven't found already a match, then see if we have + equal X for cases not(X) op X, or (not(X) op (type)X. */ + if (!op && a1expr) + { + if (operand_equal_p (arg2, a1expr, 0) + || operand_equal_p (a2strip, a1expr, 0)) + op = arg2; + } + /* Did we found no match, return NULL_TREE. */ + if (!op) + return NULL_TREE; + + /* We have found a X op not(X) operation. */ + if (code == BIT_AND_EXPR) + return integer_zero_node; + else if (code == BIT_IOR_EXPR) + { + /* If X has type precision of one, then result is 1. */ + if ((op == arg1 && operand_precision_onep (a1strip)) + || (op == arg2 && operand_precision_onep (a2strip))) + return integer_one_node; + /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ + } + else + { + /* Result for XOR for X with type precision of one is 1. */ + if ((op == arg1 && operand_precision_onep (a1strip)) + || (op == arg2 && operand_precision_onep (a2strip))) + 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. */ @@ -1840,7 +2062,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,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (char a, unsigned short b) +{ + return (a & !a) | (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-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,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned char a, _Bool b) +{ + return (!a & a) | (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-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" } } */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-06-29 12:52 ` Kai Tietz @ 2011-06-29 13:41 ` Kai Tietz 2011-06-30 12:22 ` Richard Guenther 0 siblings, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-06-29 13:41 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 3642 bytes --] ----- Original Message ----- From: "Kai Tietz" <ktietz@redhat.com> To: "Richard Guenther" <richard.guenther@gmail.com> Cc: gcc-patches@gcc.gnu.org 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" <richard.guenther@gmail.com> To: "Kai Tietz" <ktietz@redhat.com> Cc: gcc-patches@gcc.gnu.org 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 <ktietz@redhat.com> 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 <ktietz@redhat.com> > > * 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 <ktietz@redhat.com> > > * 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. Regards, Kai [-- Attachment #2: fold_fw.txt --] [-- Type: text/plain, Size: 12765 bytes --] Index: gcc-head/gcc/tree-ssa-forwprop.c =================================================================== --- gcc-head.orig/gcc/tree-ssa-forwprop.c +++ gcc-head/gcc/tree-ssa-forwprop.c @@ -1674,6 +1674,223 @@ simplify_builtin_call (gimple_stmt_itera return false; } +/* 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; +} + +/* Helper routine for simplify_bitwise_binary_1 function. + If a NOT-expression is found, the operand of the NOT-expression is + stored in NEXPR. + This function returns either the expression after the first + integral cast expression, or NAME. + 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 *nexpr) +{ + enum tree_code code = ERROR_MARK; + int seen_cast = 0; + + *nexpr = NULL_TREE; + + while (1) + { + tree op1, op2; + gimple def_stmt; + code = TREE_CODE (name); + /* If name has none-intergal type, or isn't a SSA_NAME, then + stop search. */ + if (code != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (name))) + break; + def_stmt = SSA_NAME_DEF_STMT (name); + if (!def_stmt || !is_gimple_assign (def_stmt)) + break; + + code = gimple_assign_rhs_code (def_stmt); + op1 = gimple_assign_rhs1 (def_stmt); + op2 = NULL_TREE; + + /* Is expression a conversion?. */ + if (CONVERT_EXPR_CODE_P (code)) + { + /* Just allow sinking over one cast and this only for + integeral types. Otherwise value truncation + or intermediate float conversions need to be + considered. */ + if (seen_cast) + break; + ++seen_cast; + name = op1; + continue; + } + + /* 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 break search. */ + if (code == EQ_EXPR || code == BIT_XOR_EXPR) + op2 = gimple_assign_rhs2 (def_stmt); + else if (code != TRUTH_NOT_EXPR + && code != BIT_NOT_EXPR) + break; + /* If !X or ~X is found, set NEXPR and break search. */ + if (code == TRUTH_NOT_EXPR + || (code == BIT_NOT_EXPR + && INTEGRAL_TYPE_P (name) + && operand_precision_onep (name))) + *nexpr = op1; + /* If X == 0 or X ^ 1 is found, set NEXPR and break search. */ + else if (code == EQ_EXPR || code == BIT_XOR_EXPR) + { + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) + break; + if (code == EQ_EXPR + && TREE_CODE (op2) == INTEGER_CST + && integer_zerop (op2)) + *nexpr = op1; + else if (code == EQ_EXPR + && TREE_CODE (op1) == INTEGER_CST + && integer_zerop (op1)) + *nexpr = op2; + else if (code == BIT_XOR_EXPR + && operand_precision_onep (op1) + && TREE_CODE (op2) == INTEGER_CST + && integer_onep (op2)) + *nexpr = op1; + } + break; + } + + return name; +} + +/* 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. + We also pattern match optional integral type casts on operation's + operands. + + 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 a1strip, a1expr; + tree a2strip, a2expr; + 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. */ + a1strip = detect_not_expr_operand (arg1, &a1expr); + a2strip = detect_not_expr_operand (arg2, &a2expr); + + /* If there are no not-expressions found, return NULL_TREE. */ + if (!a1expr && !a2expr) + return NULL_TREE; + + /* Do we have case not(X) op not(X)? */ + if (a1expr && a2expr) + { + /* Check if operands not(ARG1) and not(ARG2) are equal and + fold them if so. */ + if (operand_equal_p (a1expr, a2expr, 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 (a2expr) + { + /* Check if X is equal for cases X CODE not(X), or + (type) X not(X). */ + if (operand_equal_p (arg1, a2expr, 0) + || operand_equal_p (a1strip, a2expr, 0)) + op = arg1; + } + /* If haven't found already a match, then see if we have + equal X for cases not(X) op X, or (not(X) op (type)X. */ + if (!op && a1expr) + { + if (operand_equal_p (arg2, a1expr, 0) + || operand_equal_p (a2strip, a1expr, 0)) + op = arg2; + } + /* Did we found no match, return NULL_TREE. */ + if (!op) + return NULL_TREE; + + /* We have found a X op not(X) operation. */ + if (code == BIT_AND_EXPR) + return integer_zero_node; + else if (code == BIT_IOR_EXPR) + { + /* If X has type precision of one, then result is 1. */ + if (operand_precision_onep (op)) + return integer_one_node; + + /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ + } + else + { + /* Result for XOR for X with type precision of one is 1. */ + if (operand_precision_onep (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. */ @@ -1840,7 +2057,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,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (char a, unsigned short b) +{ + return (a & !a) | (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-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,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned char a, _Bool b) +{ + return (!a & a) | (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-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" } } */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-06-29 13:41 ` Kai Tietz @ 2011-06-30 12:22 ` Richard Guenther 2011-07-01 11:44 ` Kai Tietz 0 siblings, 1 reply; 14+ messages in thread From: Richard Guenther @ 2011-06-30 12:22 UTC (permalink / raw) To: Kai Tietz; +Cc: gcc-patches On Wed, Jun 29, 2011 at 3:00 PM, Kai Tietz <ktietz@redhat.com> wrote: > ----- Original Message ----- > From: "Kai Tietz" <ktietz@redhat.com> > To: "Richard Guenther" <richard.guenther@gmail.com> > Cc: gcc-patches@gcc.gnu.org > 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" <richard.guenther@gmail.com> > To: "Kai Tietz" <ktietz@redhat.com> > Cc: gcc-patches@gcc.gnu.org > 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 <ktietz@redhat.com> 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 <ktietz@redhat.com> >> >> * 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 <ktietz@redhat.com> >> >> * 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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-06-30 12:22 ` Richard Guenther @ 2011-07-01 11:44 ` Kai Tietz 2011-07-01 12:53 ` Richard Guenther 0 siblings, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-07-01 11:44 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 6953 bytes --] ----- Original Message ----- From: "Richard Guenther" <richard.guenther@gmail.com> To: "Kai Tietz" <ktietz@redhat.com> Cc: gcc-patches@gcc.gnu.org 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 <ktietz@redhat.com> wrote: > ----- Original Message ----- > From: "Kai Tietz" <ktietz@redhat.com> > To: "Richard Guenther" <richard.guenther@gmail.com> > Cc: gcc-patches@gcc.gnu.org > 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" <richard.guenther@gmail.com> > To: "Kai Tietz" <ktietz@redhat.com> > Cc: gcc-patches@gcc.gnu.org > 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 <ktietz@redhat.com> 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 <ktietz@redhat.com> >> >> * 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 <ktietz@redhat.com> >> >> * 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 <ktietz@redhat.com> * 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 <ktietz@redhat.com> * 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 [-- Attachment #2: fold_fw.txt --] [-- Type: text/plain, Size: 11518 bytes --] 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" } } */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-01 11:44 ` Kai Tietz @ 2011-07-01 12:53 ` Richard Guenther 2011-07-01 13:43 ` Kai Tietz 0 siblings, 1 reply; 14+ messages in thread From: Richard Guenther @ 2011-07-01 12:53 UTC (permalink / raw) To: Kai Tietz; +Cc: gcc-patches On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: > Ok, here is reworked patch with adjusted testcase. > > ChangeLog gcc/ > > 2011-07-01 Kai Tietz <ktietz@redhat.com> > > * 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 <ktietz@redhat.com> > > * 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? (please post patches inline) +/* Checks if expression has type of one-bit precision, or is a known + truth-value pression. */ +static bool +truth_valued_ssa_name (tree name) The function comment should refer to each parameter in capital letters. The comment is also odd, if you consider the function name. Better would be "Return true if the SSA name NAME is of truth-value. " + /* 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; Technically correct, but did you run into actual problems without this? +/* 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) What's a NOT-expression? I'd suggest /* For the SSA name NAME return an expression X so that NAME = !X. If there is no such X, return NULL_TREE. */ Then a better name for the function would be lookup_inverted_value. + def = SSA_NAME_DEF_STMT (name); + if (!def || !is_gimple_assign (def)) + return NULL_TREE; + def is never NULL. + 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)) op1, not 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; I think you want this test generally, before the switch. + if (integer_zerop (op2)) + return op1; + else if (integer_zerop (op1)) + return op2; It's always op2 that is 0, no need to test op1. What about NE_EXPR? If you allow EQ/NE_EXPRs then what this function returns is not something for which NAME = !X holds but something for which NAME = X == 0 holds. Otherwise you have to make sure op1 is a truth value. There is also EQ/NE_EXPR with op2 == 1, which at least for truth-valued op1 can be handled as well. + 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; + } + /* 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; + } gimple_fold catches this already, no reason to do that here. + /* Do we have case not(X) op not(X)? */ + if (a1not && a2not) + { CSE would have handled this, so no reason to check this - you've done this with the previous operand_equal_p test already. + /* 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; ... + if (a2not) + { + /* X equal to Y for X op not(Y) */ + if (operand_equal_p (arg1, a2not, 0)) + op = arg1; + } don't need a1not yet So I suggest to rewrite this to sth like a1not = detect_not_expr_operand (arg1); if (a1not && operand_equal_p (a1not, arg2, 0)) op = arg2; else if ((a2not = detect_not_expr_operand (arg2)) && operand_equal_p (arg1, a2not, 0)) op = arg1; else return NULL_TREE; ... as that is cheaper. The ???s below are probably not worth handling. Richard. > Regards, > Kai > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-01 12:53 ` Richard Guenther @ 2011-07-01 13:43 ` Kai Tietz 2011-07-01 13:57 ` Kai Tietz 0 siblings, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-07-01 13:43 UTC (permalink / raw) To: Richard Guenther; +Cc: Kai Tietz, gcc-patches 2011/7/1 Richard Guenther <richard.guenther@gmail.com>: > On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: >> Ok, here is reworked patch with adjusted testcase. >> >> ChangeLog gcc/ >> >> 2011-07-01 Kai Tietz <ktietz@redhat.com> >> >> * 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 <ktietz@redhat.com> >> >> * 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? > > (please post patches inline) > > +/* Checks if expression has type of one-bit precision, or is a known > + truth-value pression. */ > +static bool > +truth_valued_ssa_name (tree name) > > The function comment should refer to each parameter in capital letters. > The comment is also odd, if you consider the function name. Better > would be "Return true if the SSA name NAME is of truth-value. " Ok > + /* 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; > > Technically correct, but did you run into actual problems without this? Yes, this makes issues. See BIT_NOT_EXPR in fold-const. It uses LHS type for ~0. [*] > +/* 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) > > What's a NOT-expression? I'd suggest > > /* For the SSA name NAME return an expression X so that > NAME = !X. If there is no such X, return NULL_TREE. */ > > Then a better name for the function would be lookup_inverted_value. Hmm, we don't look up inverted values in general. May lookup_inverted_truth_value? > + def = SSA_NAME_DEF_STMT (name); > + if (!def || !is_gimple_assign (def)) > + return NULL_TREE; > + > > def is never NULL. Ok > + 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)) > > op1, not name No, name is right. see [*] > + 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; > > I think you want this test generally, before the switch. No, no need for this. Just for comparisons I need to check that operands are equal. The type of NAME is always an integral value. > + if (integer_zerop (op2)) > + return op1; > + else if (integer_zerop (op1)) > + return op2; > > It's always op2 that is 0, no need to test op1. So for comparison constant will be moved always right-hand? Ok fine by this. > What about NE_EXPR? Maybe for X != 1 for an truth-valued X. But I never saw this pattern generated. All other cases related to NE_EXPR, which might be an inverted variant aren't trivial and not sure if it is worth checking them here. Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of (X == 0 && Y == 0). But those things might be better placed in and/or_comparison folding in gimple-fold.c, isn't it? > If you allow EQ/NE_EXPRs then what this function returns is > not something for which NAME = !X holds but something > for which NAME = X == 0 holds. Otherwise you have to > make sure op1 is a truth value. !X is (for integral types) X == (type-x) 0. And this transformation is bijective AFAICS. I don't see the point you mean here. > There is also EQ/NE_EXPR with op2 == 1, which at least > for truth-valued op1 can be handled as well. See comment above. It is true that X != 1 (for truth-valued X) is X == 0. This might be a special case worth to add, but for X != 0 (for truth-valued X) it isn't. Same as for X == 1 cases. We want to return the argument of the not expression here. So we would need to return for those cases !X. > + 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; > + } > > + /* 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; > + } > > gimple_fold catches this already, no reason to do that here. Ok > + /* Do we have case not(X) op not(X)? */ > + if (a1not && a2not) > + { > > CSE would have handled this, so no reason to check this - you've > done this with the previous operand_equal_p test already. No I didn't. As this will match cases like (X ^ 1) & !X (for truth-valued X). We compare here the operand of the not-expression. > + /* 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; > > ... > > + if (a2not) > + { > + /* X equal to Y for X op not(Y) */ > + if (operand_equal_p (arg1, a2not, 0)) > + op = arg1; > + } > > don't need a1not yet > > So I suggest to rewrite this to sth like > > a1not = detect_not_expr_operand (arg1); > if (a1not > && operand_equal_p (a1not, arg2, 0)) > op = arg2; > else if ((a2not = detect_not_expr_operand (arg2)) > && operand_equal_p (arg1, a2not, 0)) > op = arg1; > else > return NULL_TREE; > > ... > > as that is cheaper. The ???s below are probably not worth handling. > > Richard. > >> Regards, >> Kai >> > Regards, Kai ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-01 13:43 ` Kai Tietz @ 2011-07-01 13:57 ` Kai Tietz 2011-07-01 15:23 ` Kai Tietz 2011-07-02 8:59 ` Kai Tietz 0 siblings, 2 replies; 14+ messages in thread From: Kai Tietz @ 2011-07-01 13:57 UTC (permalink / raw) To: Richard Guenther; +Cc: Kai Tietz, gcc-patches 2011/7/1 Kai Tietz <ktietz70@googlemail.com>: > 2011/7/1 Richard Guenther <richard.guenther@gmail.com>: >> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: >>> Ok, here is reworked patch with adjusted testcase. >>> >>> ChangeLog gcc/ >>> >>> 2011-07-01 Kai Tietz <ktietz@redhat.com> >>> >>> * 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 <ktietz@redhat.com> >>> >>> * 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? >> >> (please post patches inline) >> >> +/* Checks if expression has type of one-bit precision, or is a known >> + truth-value pression. */ >> +static bool >> +truth_valued_ssa_name (tree name) >> >> The function comment should refer to each parameter in capital letters. >> The comment is also odd, if you consider the function name. Better >> would be "Return true if the SSA name NAME is of truth-value. " > > Ok > >> + /* 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; >> >> Technically correct, but did you run into actual problems without this? > Yes, this makes issues. See BIT_NOT_EXPR in fold-const. It uses LHS type > for ~0. [*] > >> +/* 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) >> >> What's a NOT-expression? I'd suggest >> >> /* For the SSA name NAME return an expression X so that >> NAME = !X. If there is no such X, return NULL_TREE. */ >> >> Then a better name for the function would be lookup_inverted_value. > Hmm, we don't look up inverted values in general. May > lookup_inverted_truth_value? > >> + def = SSA_NAME_DEF_STMT (name); >> + if (!def || !is_gimple_assign (def)) >> + return NULL_TREE; >> + >> >> def is never NULL. > Ok > >> + 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)) >> >> op1, not name > > No, name is right. see [*] > >> + 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; >> >> I think you want this test generally, before the switch. > No, no need for this. Just for comparisons I need to check that > operands are equal. The type of NAME > is always an integral value. > >> + if (integer_zerop (op2)) >> + return op1; >> + else if (integer_zerop (op1)) >> + return op2; >> >> It's always op2 that is 0, no need to test op1. > So for comparison constant will be moved always right-hand? Ok fine by this. > >> What about NE_EXPR? > Maybe for X != 1 for an truth-valued X. But I never saw this pattern > generated. All other cases related to NE_EXPR, which might be an > inverted variant aren't trivial and not sure if it is worth checking > them here. > Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of > (X == 0 && Y == 0). But those things might be better placed in > and/or_comparison folding in gimple-fold.c, isn't it? > >> If you allow EQ/NE_EXPRs then what this function returns is >> not something for which NAME = !X holds but something >> for which NAME = X == 0 holds. Otherwise you have to >> make sure op1 is a truth value. > !X is (for integral types) X == (type-x) 0. And this transformation is > bijective AFAICS. I don't see the point you mean here. > >> There is also EQ/NE_EXPR with op2 == 1, which at least >> for truth-valued op1 can be handled as well. > > See comment above. It is true that X != 1 (for truth-valued X) is X == > 0. This might be a special case worth to add, but for X != 0 (for > truth-valued X) it isn't. Same as for X == 1 cases. We want to return > the argument of the not expression here. So we would need to return > for those cases !X. > >> + 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; >> + } >> >> + /* 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; >> + } >> >> gimple_fold catches this already, no reason to do that here. > Ok > >> + /* Do we have case not(X) op not(X)? */ >> + if (a1not && a2not) >> + { >> >> CSE would have handled this, so no reason to check this - you've >> done this with the previous operand_equal_p test already. > No I didn't. As this will match cases like (X ^ 1) & !X (for > truth-valued X). We compare here the operand of the not-expression. > >> + /* 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; >> >> ... >> >> + if (a2not) >> + { >> + /* X equal to Y for X op not(Y) */ >> + if (operand_equal_p (arg1, a2not, 0)) >> + op = arg1; >> + } >> >> don't need a1not yet >> >> So I suggest to rewrite this to sth like >> >> a1not = detect_not_expr_operand (arg1); >> if (a1not >> && operand_equal_p (a1not, arg2, 0)) >> op = arg2; >> else if ((a2not = detect_not_expr_operand (arg2)) >> && operand_equal_p (arg1, a2not, 0)) >> op = arg1; >> else >> return NULL_TREE; >> >> ... >> >> as that is cheaper. The ???s below are probably not worth handling. >> >> Richard. >> >>> Regards, >>> Kai >>> >> > > Regards, > Kai > To be more correct here about the use of the LHS for ~ X instead of using X. If I check X for truth-valued, I would match also things like ~(X == 0). But type of the comparison isn't necessarily bool, So I would match for code like 'int foo (int c) { return c & ~(c == 0); }' and would fold it to zero. But it has for c with value zero the value 0, and for c with value not zero the result c. Regards, Kai ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-01 13:57 ` Kai Tietz @ 2011-07-01 15:23 ` Kai Tietz 2011-07-04 13:17 ` Richard Guenther 2011-07-02 8:59 ` Kai Tietz 1 sibling, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-07-01 15:23 UTC (permalink / raw) To: Richard Guenther; +Cc: Kai Tietz, gcc-patches 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. */ +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; + /* See if we have in arguments logical-not patterns. */ + a1not = lookup_logical_inverted_value (arg1); + a2not = lookup_logical_inverted_value (arg2); + + /* 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.. */ + if (operand_equal_p (a1not, a2not, 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; + } + return NULL_TREE; + } + + if (a2not && operand_equal_p (arg1, a2not, 0)) + op = arg1; + else if (a1not && operand_equal_p (arg2, a1not, 0)) + op = arg2; + else + return NULL_TREE; + + /* X & !X -> 0. */ + if (code == BIT_AND_EXPR) + return integer_zero_node; + /* 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. */ + 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; } + /* 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" } } */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-01 15:23 ` Kai Tietz @ 2011-07-04 13:17 ` Richard Guenther 2011-07-04 18:55 ` Kai Tietz 0 siblings, 1 reply; 14+ messages in thread From: Richard Guenther @ 2011-07-04 13:17 UTC (permalink / raw) To: Kai Tietz; +Cc: Kai Tietz, gcc-patches 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" } } */ > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-04 13:17 ` Richard Guenther @ 2011-07-04 18:55 ` Kai Tietz 2011-07-07 14:34 ` Richard Guenther 0 siblings, 1 reply; 14+ messages in thread From: Kai Tietz @ 2011-07-04 18:55 UTC (permalink / raw) To: Richard Guenther; +Cc: Kai Tietz, gcc-patches Ok, reworked version. The folding of X op X and !X op !X seems indeed not being necessary. So function simplifies much. Bootstrapped and regression tested for all standard languages (plus Ada and Obj-C++). 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,129 @@ 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), type); + 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; +} + +/* 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 type, + tree arg1, tree arg2) +{ + tree anot; + + /* 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 + return NULL_TREE as this optimization is handled fold_stmt. */ + if (arg1 == arg2) + return NULL_TREE; + /* See if we have in arguments logical-not patterns. */ + if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE + || anot != arg2) + && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE + || anot != arg1)) + return NULL_TREE; + + /* X & !X -> 0. */ + if (code == BIT_AND_EXPR) + return fold_convert (type, integer_zero_node); + /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */ + if (truth_valued_ssa_name (anot)) + return fold_convert (type, 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. */ @@ -1769,6 +1892,15 @@ simplify_bitwise_binary (gimple_stmt_ite return true; } + /* Try simple folding for X op !X, and X op X. */ + res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2); + if (res != NULL_TREE) + { + 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" } } */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-04 18:55 ` Kai Tietz @ 2011-07-07 14:34 ` Richard Guenther 0 siblings, 0 replies; 14+ messages in thread From: Richard Guenther @ 2011-07-07 14:34 UTC (permalink / raw) To: Kai Tietz; +Cc: Kai Tietz, gcc-patches On Mon, Jul 4, 2011 at 8:55 PM, Kai Tietz <ktietz70@googlemail.com> wrote: > Ok, reworked version. The folding of X op X and !X op !X seems indeed > not being necessary. So function simplifies much. > > Bootstrapped and regression tested for all standard languages (plus > Ada and Obj-C++). Ok for apply? Ok with a proper changelog entry. Thanks, Richard. > 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,129 @@ 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), type); > + 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; > +} > + > +/* 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 type, > + tree arg1, tree arg2) > +{ > + tree anot; > + > + /* 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 > + return NULL_TREE as this optimization is handled fold_stmt. */ > + if (arg1 == arg2) > + return NULL_TREE; > + /* See if we have in arguments logical-not patterns. */ > + if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE > + || anot != arg2) > + && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE > + || anot != arg1)) > + return NULL_TREE; > + > + /* X & !X -> 0. */ > + if (code == BIT_AND_EXPR) > + return fold_convert (type, integer_zero_node); > + /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */ > + if (truth_valued_ssa_name (anot)) > + return fold_convert (type, 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. */ > > @@ -1769,6 +1892,15 @@ simplify_bitwise_binary (gimple_stmt_ite > return true; > } > > + /* Try simple folding for X op !X, and X op X. */ > + res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2); > + if (res != NULL_TREE) > + { > + 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" } } */ > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns 2011-07-01 13:57 ` Kai Tietz 2011-07-01 15:23 ` Kai Tietz @ 2011-07-02 8:59 ` Kai Tietz 1 sibling, 0 replies; 14+ messages in thread From: Kai Tietz @ 2011-07-02 8:59 UTC (permalink / raw) To: Richard Guenther; +Cc: Kai Tietz, gcc-patches 2011/7/1 Kai Tietz <ktietz70@googlemail.com>: > 2011/7/1 Kai Tietz <ktietz70@googlemail.com>: >> 2011/7/1 Richard Guenther <richard.guenther@gmail.com>: >>> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: >>>> Ok, here is reworked patch with adjusted testcase. >>>> >>>> ChangeLog gcc/ >>>> >>>> 2011-07-01 Kai Tietz <ktietz@redhat.com> >>>> >>>> * 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 <ktietz@redhat.com> >>>> >>>> * 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? >>> >>> (please post patches inline) >>> >>> +/* Checks if expression has type of one-bit precision, or is a known >>> + truth-value pression. */ >>> +static bool >>> +truth_valued_ssa_name (tree name) >>> >>> The function comment should refer to each parameter in capital letters. >>> The comment is also odd, if you consider the function name. Better >>> would be "Return true if the SSA name NAME is of truth-value. " >> >> Ok >> >>> + /* 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; >>> >>> Technically correct, but did you run into actual problems without this? >> Yes, this makes issues. See BIT_NOT_EXPR in fold-const. It uses LHS type >> for ~0. [*] >> >>> +/* 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) >>> >>> What's a NOT-expression? I'd suggest >>> >>> /* For the SSA name NAME return an expression X so that >>> NAME = !X. If there is no such X, return NULL_TREE. */ >>> >>> Then a better name for the function would be lookup_inverted_value. >> Hmm, we don't look up inverted values in general. May >> lookup_inverted_truth_value? >> >>> + def = SSA_NAME_DEF_STMT (name); >>> + if (!def || !is_gimple_assign (def)) >>> + return NULL_TREE; >>> + >>> >>> def is never NULL. >> Ok >> >>> + 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)) >>> >>> op1, not name >> >> No, name is right. see [*] >> >>> + 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; >>> >>> I think you want this test generally, before the switch. >> No, no need for this. Just for comparisons I need to check that >> operands are equal. The type of NAME >> is always an integral value. >> >>> + if (integer_zerop (op2)) >>> + return op1; >>> + else if (integer_zerop (op1)) >>> + return op2; >>> >>> It's always op2 that is 0, no need to test op1. >> So for comparison constant will be moved always right-hand? Ok fine by this. >> >>> What about NE_EXPR? >> Maybe for X != 1 for an truth-valued X. But I never saw this pattern >> generated. All other cases related to NE_EXPR, which might be an >> inverted variant aren't trivial and not sure if it is worth checking >> them here. >> Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of >> (X == 0 && Y == 0). But those things might be better placed in >> and/or_comparison folding in gimple-fold.c, isn't it? >> >>> If you allow EQ/NE_EXPRs then what this function returns is >>> not something for which NAME = !X holds but something >>> for which NAME = X == 0 holds. Otherwise you have to >>> make sure op1 is a truth value. >> !X is (for integral types) X == (type-x) 0. And this transformation is >> bijective AFAICS. I don't see the point you mean here. >> >>> There is also EQ/NE_EXPR with op2 == 1, which at least >>> for truth-valued op1 can be handled as well. >> >> See comment above. It is true that X != 1 (for truth-valued X) is X == >> 0. This might be a special case worth to add, but for X != 0 (for >> truth-valued X) it isn't. Same as for X == 1 cases. We want to return >> the argument of the not expression here. So we would need to return >> for those cases !X. >> >>> + 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; >>> + } >>> >>> + /* 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; >>> + } >>> >>> gimple_fold catches this already, no reason to do that here. >> Ok >> >>> + /* Do we have case not(X) op not(X)? */ >>> + if (a1not && a2not) >>> + { >>> >>> CSE would have handled this, so no reason to check this - you've >>> done this with the previous operand_equal_p test already. >> No I didn't. As this will match cases like (X ^ 1) & !X (for >> truth-valued X). We compare here the operand of the not-expression. >> >>> + /* 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; >>> >>> ... >>> >>> + if (a2not) >>> + { >>> + /* X equal to Y for X op not(Y) */ >>> + if (operand_equal_p (arg1, a2not, 0)) >>> + op = arg1; >>> + } >>> >>> don't need a1not yet >>> >>> So I suggest to rewrite this to sth like >>> >>> a1not = detect_not_expr_operand (arg1); >>> if (a1not >>> && operand_equal_p (a1not, arg2, 0)) >>> op = arg2; >>> else if ((a2not = detect_not_expr_operand (arg2)) >>> && operand_equal_p (arg1, a2not, 0)) >>> op = arg1; >>> else >>> return NULL_TREE; >>> >>> ... >>> >>> as that is cheaper. The ???s below are probably not worth handling. >>> >>> Richard. >>> >>>> Regards, >>>> Kai >>>> >>> >> >> Regards, >> Kai >> > > To be more correct here about the use of the LHS for ~ X instead of > using X. If I check X for truth-valued, I would match also things like > ~(X == 0). But type of the comparison isn't necessarily bool, So I > would match for code like 'int foo (int c) { return c & ~(c == 0); }' > and would fold it to zero. But it has for c with value zero the value > 0, and for c with value not zero the result c. Sorry, yesterday wasn't my day. Of course I meant sample 'int foo c) { return c & ~ (c != 0); }'. Its result for c != 0 is (c & 0xfffffffe), and for c == 0 it is 0. Kai ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2011-07-07 13:44 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <196308741.816832.1309273513615.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com>
2011-06-28 15:40 ` [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns Kai Tietz
2011-06-29 11:28 ` Richard Guenther
2011-06-29 12:52 ` Kai Tietz
2011-06-29 13:41 ` Kai Tietz
2011-06-30 12:22 ` Richard Guenther
2011-07-01 11:44 ` Kai Tietz
2011-07-01 12:53 ` Richard Guenther
2011-07-01 13:43 ` Kai Tietz
2011-07-01 13:57 ` Kai Tietz
2011-07-01 15:23 ` Kai Tietz
2011-07-04 13:17 ` Richard Guenther
2011-07-04 18:55 ` Kai Tietz
2011-07-07 14:34 ` Richard Guenther
2011-07-02 8:59 ` Kai Tietz
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).