From patchwork Fri Oct 7 16:39:01 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 118350 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 024B1B70FF for ; Sat, 8 Oct 2011 03:39:42 +1100 (EST) Received: (qmail 16254 invoked by alias); 7 Oct 2011 16:39:26 -0000 Received: (qmail 15819 invoked by uid 22791); 7 Oct 2011 16:39:18 -0000 X-SWARE-Spam-Status: No, hits=-1.8 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-vw0-f47.google.com (HELO mail-vw0-f47.google.com) (209.85.212.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 07 Oct 2011 16:39:02 +0000 Received: by vwe42 with SMTP id 42so3778583vwe.20 for ; Fri, 07 Oct 2011 09:39:01 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.91.11 with SMTP id ca11mr3451167vdb.8.1318005541361; Fri, 07 Oct 2011 09:39:01 -0700 (PDT) Received: by 10.220.180.5 with HTTP; Fri, 7 Oct 2011 09:39:01 -0700 (PDT) Date: Fri, 7 Oct 2011 18:39:01 +0200 Message-ID: Subject: [patch tree-optimization]: 3 of 6 Improve reassoc for bitwise operations From: Kai Tietz To: GCC Patches Cc: Richard Guenther 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 Hello, This patch adds to the break-up pass the facility to expand (X | Y) ==/!= 0 expression. This enables in later reassociation pass better results. ChangeLog 2011-10-07 Kai Tietz * tree-ssa-reassoc.c (expand_cmp_ior): Helper for expanding (X | Y) ==/!= 0 statments. (break_up_bitwise_combined_stmt): Make use of expand_cmp_ior. 2011-10-07 Kai Tietz * gcc.dg/tree-ssa/reassoc-cmpior-1.c: New file. * gcc.dg/tree-ssa/reassoc-cmpior-2.c: New file. * gcc.dg/tree-ssa/reassoc-cmpior-3.c: New file. Bootstrapped and regression-tested for all languages plus Ada and Obj-C++ on x86_64-pc-linux-gnu. Ok for apply? Regards, Kai Index: gcc/gcc/tree-ssa-reassoc.c =================================================================== --- gcc.orig/gcc/tree-ssa-reassoc.c +++ gcc/gcc/tree-ssa-reassoc.c @@ -59,6 +59,8 @@ static void remove_stmt_chain (tree); it would promote the reassociation of adds. 1.2. Breaking up to normalized form for bitwise-not operations on bitwise-binary and for bitwise-not operation on compares. + 1.3 Breaking up combined expression made out of boolean-typed bitwise + expressions for improving simplification. 2. Left linearization of the expression trees, so that (A+B)+(C+D) becomes (((A+B)+C)+D), which is easier for us to rewrite later. @@ -712,8 +714,89 @@ expand_not_bitwise_binary (tree type, tr NULL_TREE, expr); } +/* Routine to expand (X | Y) ==/!= 0 and doing + simplification on (X cmp Y) ==/!= 0. + - (X | Y) == 0 to (X == 0) & (Y == 0) + - (X | Y) != 0 to (X != 0) | (Y != 0). + - (X cmp Y) == 0 to (X cmp' Y) with cmp'=invert of cmp. + - (X cmp Y) != 0 to (X cmp Y). + + The argument CODE can be either NE_EXPR, or EQ_EXPR. It indicates + what kind of expansion is performed. */ + +static tree +expand_cmp_ior (tree op, tree type, enum tree_code code) +{ + tree op1, op2; + gimple s = NULL; + enum tree_code hcode; + + /* Handle integral constant value case. */ + if (TREE_CODE (op) == INTEGER_CST) + { + if (code == EQ_EXPR) + return fold_convert (type, (integer_zerop (op) ? integer_one_node + : integer_zero_node)); + return fold_convert (type, (!integer_zerop (op) ? integer_one_node + : integer_zero_node)); + } + + /* If operand OP isn't a gimple-assign, or has non-single use, + then simply creat a comparison != 0 for it. */ + if (TREE_CODE (op) != SSA_NAME + || !(s = SSA_NAME_DEF_STMT (op)) + || !is_gimple_assign (s) + || !has_single_use (op)) + return make_new_tmp_statement (type, code, op, + build_zero_cst (TREE_TYPE (op)), s); + + hcode = gimple_assign_rhs_code (s); + + /* Operand code of OP isn't of comparison kind, and not + a bitwise-not, then creat a comparison != 0 for it. */ + if (TREE_CODE_CLASS (hcode) != tcc_comparison + && hcode != BIT_IOR_EXPR) + return make_new_tmp_statement (type, code, op, + build_zero_cst (TREE_TYPE (op)), s); + + op1 = gimple_assign_rhs1 (s); + op2 = gimple_assign_rhs2 (s); + + /* Simplify (X cmp Y) != 0 -> (X cmp Y), and + (X cmp Y) == 0 -> X cnp' Y, with cmp' = inverted cmp. */ + if (TREE_CODE_CLASS (hcode) == tcc_comparison) + { + tree op1type = TREE_TYPE (op1); + + if (code == EQ_EXPR) + { + enum tree_code ncode; + ncode = invert_tree_comparison (hcode, + HONOR_NANS (TYPE_MODE (op1type))); + if (ncode != ERROR_MARK) + return make_new_tmp_statement (type, ncode, op1, op2, s); + } + else + return make_new_tmp_statement (type, hcode, op1, op2, s); + } + + /* Break up (X | Y) ==/!= 0 case. */ + if (hcode == BIT_IOR_EXPR) + { + op1 = expand_cmp_ior (op1, type, code); + op2 = expand_cmp_ior (op2, type, code); + return make_new_tmp_statement (type, (code == EQ_EXPR ? BIT_AND_EXPR + : BIT_IOR_EXPR), + op1, op2, s); + } + return make_new_tmp_statement (type, code, op, + build_zero_cst (TREE_TYPE (op)), s); +} + + /* Break up STMT if it is a combined statement made out of - bitwise operations. Handle expansion of ~(A op B). */ + bitwise operations. Handle expansion of ~(A op B), and + (A | B) !=/== 0. */ static bool break_up_bitwise_combined_stmt (gimple stmt) @@ -728,9 +811,13 @@ break_up_bitwise_combined_stmt (gimple s old_op1 = op1; old_op2 = op2 = NULL_TREE; + if (code == EQ_EXPR || code == NE_EXPR) + old_op2 = op2 = gimple_assign_rhs2 (stmt); + /* Check that CODE can be handled and that left-hand operand is of kind SSA_NAME. */ - if (code != BIT_NOT_EXPR + if ((code != BIT_NOT_EXPR + && code != EQ_EXPR && code != NE_EXPR) || TREE_CODE (op1) != SSA_NAME) return false; @@ -742,8 +829,42 @@ break_up_bitwise_combined_stmt (gimple s || !has_single_use (op1)) return false; - /* Handle expansion for ~X. */ - if (code == BIT_NOT_EXPR) + if (code == NE_EXPR || code == EQ_EXPR) + { + tree inner_op1, inner_op2; + + /* Check that operands have integral type and + see if it has as second argument a constant zero valued + operand. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)) + || TREE_CODE (op2) != INTEGER_CST + || !integer_zerop (op2)) + return false; + + /* Check for pattern X | Y == 0 and X | Y != 0 */ + if (gimple_assign_rhs_code (op1_def) != BIT_IOR_EXPR) + return false; + + inner_op1 = gimple_assign_rhs1 (op1_def); + inner_op2 = gimple_assign_rhs2 (op1_def); + + /* Expand (X | Y) == 0 -> (X == 0) & (Y == 0) + and (X | Y) != 0 -> (X != 0) | (Y != 0) */ + + op1 = expand_cmp_ior (inner_op1, type, code); + op2 = expand_cmp_ior (inner_op2, type, code); + + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, (code == NE_EXPR ? BIT_IOR_EXPR + : BIT_AND_EXPR), + op1, op2); + update_stmt (gsi_stmt (gsi)); + remove_stmt_chain (old_op1); + remove_stmt_chain (old_op2); + return true; + } + /* Handle expansion for expansion of ~X. */ + else if (code == BIT_NOT_EXPR) { enum tree_code inner_code = gimple_assign_rhs_code (op1_def); @@ -3091,6 +3212,10 @@ can_reassociate_p (tree op) If A or B are comparisons or are bitwise-not statement, then sink bit-not into expression, if it is a single-use statement. + Break up (X | Y) == 0 into (X == 0) & (Y == 0). + + Break up (X | Y) != 0 into (X != 0) | (Y != 0). + En passant, clear the GIMPLE visited flag on every statement. */ static void Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-1.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-1.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, int b, int c, int d) +{ + int r1 = (a | b | c) == 0; + int r2 = (a | d | c) != 0 | b == 0; + return (r1 == 0 | r2 != 0); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ + Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-2.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-2.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, int b, int c, int d) +{ + int r1 = a != 0 & c != 0 & b != 0; + int r2 = a == 0 | b != 0 | d == 0; + return (r1 == 0 | r2 != 0); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ + Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-3.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-3.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, int b, int c, int d) +{ + int r1 = a != 0 & c != 0 & b != 0; + int r2 = a == 0 | b != 0 | d == 0; + return (r1 != 0 & r2 == 0); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ +