From patchwork Wed Jun 29 11:33:30 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 102568 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 893BDB6F5C for ; Wed, 29 Jun 2011 21:33:52 +1000 (EST) Received: (qmail 17589 invoked by alias); 29 Jun 2011 11:33:50 -0000 Received: (qmail 17574 invoked by uid 22791); 29 Jun 2011 11:33:48 -0000 X-SWARE-Spam-Status: No, hits=-6.8 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx4-phx2.redhat.com (HELO mx4-phx2.redhat.com) (209.132.183.25) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 29 Jun 2011 11:33:31 +0000 Received: from mail06.corp.redhat.com (zmail06.collab.prod.int.phx2.redhat.com [10.5.5.45]) by mx4-phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p5TBXUV6013907; Wed, 29 Jun 2011 07:33:30 -0400 Date: Wed, 29 Jun 2011 07:33:30 -0400 (EDT) From: Kai Tietz To: Richard Guenther Cc: gcc-patches@gcc.gnu.org Message-ID: <1797980853.837087.1309347210741.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com> In-Reply-To: Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns MIME-Version: 1.0 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org ----- Original Message ----- From: "Richard Guenther" To: "Kai Tietz" 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 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   > >        * 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   > >        * 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 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" } } */