From patchwork Mon Jul 4 18:55:22 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 103156 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 C9CCEB6F64 for ; Tue, 5 Jul 2011 04:55:42 +1000 (EST) Received: (qmail 8193 invoked by alias); 4 Jul 2011 18:55:39 -0000 Received: (qmail 8183 invoked by uid 22791); 4 Jul 2011 18:55:38 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_ENVFROM_END_DIGIT, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-qw0-f47.google.com (HELO mail-qw0-f47.google.com) (209.85.216.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 04 Jul 2011 18:55:23 +0000 Received: by qwh5 with SMTP id 5so3044967qwh.20 for ; Mon, 04 Jul 2011 11:55:22 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.86.135 with SMTP id s7mr3473234qcl.152.1309805722549; Mon, 04 Jul 2011 11:55:22 -0700 (PDT) Received: by 10.229.65.225 with HTTP; Mon, 4 Jul 2011 11:55:22 -0700 (PDT) In-Reply-To: References: <2017997593.883643.1309520672925.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com> Date: Mon, 4 Jul 2011 20:55:22 +0200 Message-ID: Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns From: Kai Tietz To: Richard Guenther Cc: Kai Tietz , gcc-patches@gcc.gnu.org X-IsSubscribed: yes 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 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" } } */