From patchwork Fri Jul 1 11:44:32 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 102899 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 532EEB6F5B for ; Fri, 1 Jul 2011 21:45:02 +1000 (EST) Received: (qmail 2126 invoked by alias); 1 Jul 2011 11:44:53 -0000 Received: (qmail 1794 invoked by uid 22791); 1 Jul 2011 11:44:50 -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; Fri, 01 Jul 2011 11:44:33 +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 p61BiWE1011609; Fri, 1 Jul 2011 07:44:33 -0400 Date: Fri, 1 Jul 2011 07:44:32 -0400 (EDT) From: Kai Tietz To: Richard Guenther Cc: gcc-patches@gcc.gnu.org Message-ID: <2017997593.883643.1309520672925.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: 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 wrote: > ----- Original Message ----- > From: "Kai Tietz" > To: "Richard Guenther" > 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" > 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 > > 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 * 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 * gcc.dg/binop-notand1a.c: New test. * gcc.dg/binop-notand2a.c: New test. * gcc.dg/binop-notand3a.c: New test. * gcc.dg/binop-notand4a.c: New test. * gcc.dg/binop-notand5a.c: New test. * gcc.dg/binop-notand6a.c: New test. * gcc.dg/binop-notor1.c: New test. * gcc.dg/binop-notor2.c: New test. * gcc.dg/binop-notxor1.c: New test. * gcc.dg/binop-notxor2.c: New test. Bootstrapped and regression tested for all standard languages plus Ada and Obj-C++ for x86_64-pc-linux-gnu. Ok for apply? Regards, Kai Index: gcc-head/gcc/tree-ssa-forwprop.c =================================================================== --- gcc-head.orig/gcc/tree-ssa-forwprop.c +++ gcc-head/gcc/tree-ssa-forwprop.c @@ -1602,6 +1602,179 @@ simplify_builtin_call (gimple_stmt_itera return false; } +/* Checks if expression has type of one-bit precision, or is a known + truth-value pression. */ +static bool +truth_valued_ssa_name (tree name) +{ + gimple def; + tree type = TREE_TYPE (name); + + if (!INTEGRAL_TYPE_P (type)) + return false; + /* Don't check here for BOOLEAN_TYPE as the precision isn't + necessarily one and so ~X is not equal to !X. */ + if (TYPE_PRECISION (type) == 1) + return true; + def = SSA_NAME_DEF_STMT (name); + if (is_gimple_assign (def)) + return truth_value_p (gimple_assign_rhs_code (def)); + return false; +} + +/* Helper routine for simplify_bitwise_binary_1 function. + If a NOT-expression is found, the operand of the NOT-expression is + returned. Othewise NULL_TREE is returned. + Detected not-patterns are !X or X == 0 for X with integral type, and + X ^ 1 or ~X for X with integral type with precision of one. + The value of CNT_CASTS is either zero, or one. */ +static tree +detect_not_expr_operand (tree name) +{ + tree op1, op2; + enum tree_code code; + gimple def; + + /* If name has none-intergal type, or isn't a SSA_NAME, then + return. */ + if (TREE_CODE (name) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (name))) + return NULL_TREE; + def = SSA_NAME_DEF_STMT (name); + if (!def || !is_gimple_assign (def)) + return NULL_TREE; + + code = gimple_assign_rhs_code (def); + op1 = gimple_assign_rhs1 (def); + op2 = NULL_TREE; + + /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand. + If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR, + or BIT_NOT_EXPR, then return. */ + if (code == EQ_EXPR || code == BIT_XOR_EXPR) + op2 = gimple_assign_rhs2 (def); + + switch (code) + { + case TRUTH_NOT_EXPR: + return op1; + case BIT_NOT_EXPR: + if (truth_valued_ssa_name (name)) + return op1; + break; + case EQ_EXPR: + /* Check if we have X == 0 and X has an integral type. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) + break; + if (integer_zerop (op2)) + return op1; + else if (integer_zerop (op1)) + return op2; + break; + case BIT_XOR_EXPR: + /* Check if we have X ^ 1 and X is truth valued. */ + if (integer_onep (op2) && truth_valued_ssa_name (op1)) + return op1; + break; + default: + break; + } + + return NULL_TREE; +} + +/* Try to optimize patterns X & not(X) -> zero, X | not(X) -> one, and + X ^ not(X) -> one, if type of X is valid for this. + Additional handle the variants X & X -> X, X | X -> X, and X ^ X -> zero. + + See for detected not-patterns the detect_not_expr_operand function. */ +static tree +simplify_bitwise_binary_1 (enum tree_code code, tree arg1, + tree arg2) +{ + tree a1not, a2not; + tree op = NULL_TREE; + + /* If CODE isn't a bitwise binary operation, return NULL_TREE. */ + if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR + && code != BIT_XOR_EXPR) + return NULL_TREE; + + /* First check if operands ARG1 and ARG2 are equal, if so we + won't have a NOT-pattern match. Fold these patterns, as + we have detected it already. */ + if (operand_equal_p (arg1, arg2, 0)) + { + /* X & X -> X, and X | X -> X. */ + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + /* X ^ X -> 0. */ + return integer_zero_node; + } + /* Get for each operation operand its optional by one integral typed + cast stripped argument. And get the not-expression's operand, if + argument represents an not-expression. */ + a1not = detect_not_expr_operand (arg1); + a2not = detect_not_expr_operand (arg2); + + /* If there are no not-expressions found, return NULL_TREE. */ + if (!a1not && !a2not) + return NULL_TREE; + + /* Do we have case not(X) op not(X)? */ + if (a1not && a2not) + { + /* Check if operands not(ARG1) and not(ARG2) are equal and + fold them if so. */ + if (operand_equal_p (a1not, a2not, 0)) + { + /* !X & !X -> !X, and !X | i!X -> !X. */ + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + /* !X ^ !X -> 0. */ + return integer_zero_node; + } + return NULL_TREE; + } + + if (a2not) + { + /* X equal to Y for X op not(Y) */ + if (operand_equal_p (arg1, a2not, 0)) + op = arg1; + } + if (!op && a1not) + { + /* X equal to Y for not(X) op Y */ + if (operand_equal_p (arg2, a1not, 0)) + op = arg2; + } + /* No match, return NULL_TREE. */ + if (!op) + return NULL_TREE; + + /* X & not(X) -> 0. */ + if (code == BIT_AND_EXPR) + return integer_zero_node; + else if (code == BIT_IOR_EXPR) + { + /* X | not(X) -> 1, if X is truth-valued. */ + if (truth_valued_ssa_name (op)) + return integer_one_node; + + /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ + } + else if (code == BIT_XOR_EXPR) + { + /* X ^ not(X) -> 1, if X is truth-valued. */ + if (truth_valued_ssa_name (op)) + return integer_one_node; + + /* ??? Otherwise result is (X != 0 ? X : 1. not handled. */ + } + return NULL_TREE; +} + /* Simplify bitwise binary operations. Return true if a transformation applied, otherwise return false. */ @@ -1768,7 +1941,31 @@ simplify_bitwise_binary (gimple_stmt_ite update_stmt (stmt); return true; } + /* Try simple folding for X op !X, and X op X. */ + res = simplify_bitwise_binary_1 (code, arg1, arg2); + if (res != NULL_TREE && TREE_CODE (res) == INTEGER_CST) + { + res = fold_convert_loc (gimple_location (stmt), + TREE_TYPE (arg1), res); + gimple_assign_set_rhs_from_tree (gsi, res); + update_stmt (gsi_stmt (*gsi)); + return true; + } + else if (res) + { + if (!useless_type_conversion_p (TREE_TYPE (arg1), TREE_TYPE (res))) + { + res = force_gimple_operand_gsi (gsi, res, true, NULL_TREE, true, + GSI_SAME_STMT); + gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR, + res, NULL_TREE, NULL_TREE); + } + else + gimple_assign_set_rhs_from_tree (gsi, res); + update_stmt (gsi_stmt (*gsi)); + return true; + } return false; } Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (char a, unsigned short b) +{ + return (a & !a) | (b & !b); +} + +/* As long as comparisons aren't boolified and casts from boolean-types + aren't preserved, the folding of X & !X to zero fails. */ +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a) +{ + return (!a & 1) != (a == 0); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (short a) +{ + return (!a & 1) != ((a == 0) & 1); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned char a, _Bool b) +{ + return (!a & a) | (b & !b); +} + +/* As long as comparisons aren't boolified and casts from boolean-types + aren't preserved, the folding of X & !X to zero fails. */ +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (long a, unsigned long b) +{ + return (a & (a == 0)) | (b & !b); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned long a, long b) +{ + return (a & !a) | (b & (b == 0)); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a | !a) | (!b | b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a | (a == 0)) | ((b ^ 1) | b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a ^ !a) | (!b ^ b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c =================================================================== --- /dev/null +++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a ^ (a == 0)) | ((b == 0) ^ b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */