From patchwork Fri Oct 7 16:38:54 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 118349 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 91F4CB70FF for ; Sat, 8 Oct 2011 03:39:34 +1100 (EST) Received: (qmail 16037 invoked by alias); 7 Oct 2011 16:39:24 -0000 Received: (qmail 15820 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-vx0-f175.google.com (HELO mail-vx0-f175.google.com) (209.85.220.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 07 Oct 2011 16:38:55 +0000 Received: by vcbfl17 with SMTP id fl17so3847111vcb.20 for ; Fri, 07 Oct 2011 09:38:54 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.22.9 with SMTP id z9mr3462478vde.59.1318005534386; Fri, 07 Oct 2011 09:38:54 -0700 (PDT) Received: by 10.220.180.5 with HTTP; Fri, 7 Oct 2011 09:38:54 -0700 (PDT) Date: Fri, 7 Oct 2011 18:38:54 +0200 Message-ID: Subject: [patch tree-optimization]: 1 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 sink bitwise-not operations into bitwise-binary expressions. Additionally it handles special cases for ~(~X), and ~(X cmp Y). ChangeLog 2011-10-07 Kai Tietz * tree-ssa-reassoc.c (remove_stmt_chain): Helper function to remove gimple-assignment tree with all arms. (make_new_tmp_statement): Helper function to create temporary register expression. (expand_not_bitwise_binary): Perform bitwise-not operation on gimple-assignment tree. (break_up_bitwise_combined_stmt): Break-up handler for bitwise- operations. (break_up_expr_bb): Adjust to call break_up_bitwise_combined_stmt. 2011-10-07 Kai Tietz * gcc.dg/tree-ssa/reassoc-not-1.c: New file. * gcc.dg/tree-ssa/reassoc-not-2.c: New file. * gcc.dg/tree-ssa/reassoc-not-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 @@ -46,6 +46,7 @@ along with GCC; see the file COPYING3. /* Forwarders. */ static gimple build_and_add_sum (tree, tree, tree, enum tree_code); +static void remove_stmt_chain (tree); /* This is a simple global reassociation pass. It is, in part, based on the LLVM pass of the same name (They do some things more/less @@ -53,8 +54,11 @@ static gimple build_and_add_sum (tree, t It consists of five steps: - 1. Breaking up subtract operations into addition + negate, where + 1. Breaking up expressions + 1.1. Breaking up subtract operations into addition + negate, where 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. 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. @@ -560,6 +564,265 @@ get_unary_op (tree name, enum tree_code return NULL_TREE; } +/* Create a temporary register expression with type TYPE, tree code CODE, and + operands OP1 and OP2. If REF_DEF is a valid gimple statement, we use its + location information for new generated temporary. + Function returns left-hand-side of new generated temporary register. */ + +static tree +make_new_tmp_statement (tree type, enum tree_code code, tree op1, tree op2, + gimple ref_def) +{ + gimple sum; + tree tmpvar = create_tmp_reg (type, NULL); + add_referenced_var (tmpvar); + sum = build_and_add_sum (tmpvar, op1, op2, code); + if (ref_def) + gimple_set_location (sum, gimple_location (ref_def)); + return gimple_get_lhs (sum); +} + +/* Perform on tree LHS with optional definition statement EXPR + the logic-not operation. TYPE is of kind boolean. */ + +static tree +expand_not_bitwise_binary (tree type, tree lhs, gimple expr) +{ + enum tree_code code = ERROR_MARK; + tree op1 = NULL, op2 = NULL; + gimple s1 = NULL, s2 = NULL; + + if (TREE_CODE (lhs) == INTEGER_CST) + return fold_build1 (BIT_NOT_EXPR, type, lhs); + + if (expr && is_gimple_assign (expr)) + code = gimple_assign_rhs_code (expr); + + /* If statement lhs isn't a single-use statement, + we don't want to modify it. So we can do only default-case + operation for it. */ + if (code != ERROR_MARK && !has_single_use (lhs)) + code = ERROR_MARK; + + if (TREE_CODE_CLASS (code) == tcc_comparison + || code == BIT_XOR_EXPR + || code == BIT_AND_EXPR + || code == BIT_IOR_EXPR) + { + op1 = gimple_assign_rhs1 (expr); + op2 = gimple_assign_rhs2 (expr); + } + /* ~(~X) -> X. */ + else if (code == BIT_NOT_EXPR) + return gimple_assign_rhs1 (expr); + else + return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs, + NULL_TREE, expr); + + /* ~(X cmp Y) -> X cmp' Y, with cmp'=inverted comparison code, if allowed. + Otherwise fall through to default case. */ + if (TREE_CODE_CLASS (code) == tcc_comparison) + { + enum tree_code ncode; + tree op1type = TREE_TYPE (op1); + + ncode = invert_tree_comparison (code, + HONOR_NANS (TYPE_MODE (op1type))); + if (ncode != ERROR_MARK) + return make_new_tmp_statement (type, ncode, op1, op2, expr); + } + /* Handle transformation for ~(A & B) -> ~A | ~B or ~(A | B) -> ~A & ~B. */ + else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + { + /* See if left-hand operand is a gimple-assign, and has single-use. */ + if (TREE_CODE (op1) != SSA_NAME + || !(s1 = SSA_NAME_DEF_STMT (op1)) + || !is_gimple_assign (s1) + || !has_single_use (op1)) + s1 = NULL; + /* See if right-hand operand is a gimple-assign, and has + single-use. */ + if (TREE_CODE (op2) != SSA_NAME + || !(s2 = SSA_NAME_DEF_STMT (op2)) + || !is_gimple_assign (s2) + || !has_single_use (op2)) + s2 = NULL; + + /* We have to do inversion in one step to avoid looping. */ + op1 = expand_not_bitwise_binary (type, op1, s1); + op2 = expand_not_bitwise_binary (type, op2, s2); + + code = (code == BIT_AND_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR); + + if (TREE_CODE (op2) == INTEGER_CST) + { + if ((code == BIT_AND_EXPR && integer_zerop (op2)) + || (code == BIT_IOR_EXPR && integer_all_onesp (op2))) + { + remove_stmt_chain (op1); + return op2; + } + else if ((code == BIT_AND_EXPR && integer_all_onesp (op2)) + || (code == BIT_IOR_EXPR && integer_zerop (op2))) + return op1; + } + return make_new_tmp_statement (type, code, op1, op2, expr); + } + /* ~(A ^ B) -> ~A ^ B. Handle here special cases for B being + an integer constant, or being a logical-not. */ + else if (code == BIT_XOR_EXPR) + { + /* See if left-hand operand is a gimple-assign, and has single-use. */ + if (TREE_CODE (op1) != SSA_NAME + || !(s1 = SSA_NAME_DEF_STMT (op1)) + || !is_gimple_assign (s1) + || !has_single_use (op1)) + s1 = NULL; + /* See if right-hand operand is a gimple-assign, and has + single-use. */ + if (TREE_CODE (op2) != SSA_NAME + || !(s2 = SSA_NAME_DEF_STMT (op2)) + || !is_gimple_assign (s2) + || !has_single_use (op2)) + s2 = NULL; + + /* If right-hand operand isn't a bit-not expression and not + an integeral constant, then we apply bit-not on left-hand + operand. */ + if (TREE_CODE (op2) != INTEGER_CST + && (!s2 || gimple_assign_rhs_code (s2) != BIT_NOT_EXPR)) + op1 = expand_not_bitwise_binary (type, op1, s1); + else + op2 = expand_not_bitwise_binary (type, op2, s2); + + if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2)) + return op1; + if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2)) + { + remove_stmt_chain (op2); + return make_new_tmp_statement (type, BIT_NOT_EXPR, op1, NULL, expr); + } + return make_new_tmp_statement (type, BIT_XOR_EXPR, op1, op2, expr); + } + + gcc_assert (types_compatible_p (type, TREE_TYPE (lhs))); + + /* Default case lhs -> ~lhs */ + return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs, + NULL_TREE, expr); +} + +/* Break up STMT if it is a combined statement made out of + bitwise operations. Handle expansion of ~(A op B). */ + +static bool +break_up_bitwise_combined_stmt (gimple stmt) +{ + tree op1, op2, old_op1, old_op2; + gimple op1_def, op2_def; + enum tree_code code = gimple_assign_rhs_code (stmt); + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + gimple_stmt_iterator gsi; + + op1 = gimple_assign_rhs1 (stmt); + old_op1 = op1; + old_op2 = op2 = NULL_TREE; + + /* Check that CODE can be handled and that left-hand operand + is of kind SSA_NAME. */ + if (code != BIT_NOT_EXPR + || TREE_CODE (op1) != SSA_NAME) + return false; + + /* If left-hand operand isn't a gimple-assign, or isn't single-used, + the we can't do anything. */ + op1_def = SSA_NAME_DEF_STMT (op1); + if (!op1_def + || !is_gimple_assign (op1_def) + || !has_single_use (op1)) + return false; + + /* Handle expansion for ~X. */ + if (code == BIT_NOT_EXPR) + { + enum tree_code inner_code = gimple_assign_rhs_code (op1_def); + + if (inner_code == BIT_NOT_EXPR) + { + op1 = gimple_assign_rhs1 (op1_def); + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_from_tree (&gsi, op1); + update_stmt (gsi_stmt (gsi)); + remove_stmt_chain (old_op1); + return true; + } + else if (TREE_CODE_CLASS (inner_code) == tcc_comparison) + { + enum tree_code ncode; + tree op1type; + + op1 = gimple_assign_rhs1 (op1_def); + op2 = gimple_assign_rhs2 (op1_def); + op1type = TREE_TYPE (op1); + ncode = invert_tree_comparison (inner_code, + HONOR_NANS (TYPE_MODE (op1type))); + if (ncode == ERROR_MARK) + return false; + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, ncode, op1, op2); + update_stmt (gsi_stmt (gsi)); + remove_stmt_chain (old_op1); + return true; + } + if (inner_code != BIT_AND_EXPR && inner_code != BIT_IOR_EXPR + && inner_code != BIT_XOR_EXPR) + return false; + + op1 = gimple_assign_rhs1 (op1_def); + op2 = gimple_assign_rhs2 (op1_def); + + op1_def = op2_def = NULL; + + if (TREE_CODE (op1) != SSA_NAME + || (op1_def = SSA_NAME_DEF_STMT (op1)) == NULL + || !is_gimple_assign (op1_def)) + op1_def = NULL; + + if (TREE_CODE (op2) != SSA_NAME + || (op2_def = SSA_NAME_DEF_STMT (op2)) == NULL + || !is_gimple_assign (op2_def)) + op2_def = NULL; + + /* Transform as best representation either from + ~(X ^ Y) to ~X ^ Y, or from ~(X ^ Y) to X ^ Y. */ + if (inner_code == BIT_XOR_EXPR) + { + if (TREE_CODE (op2) != INTEGER_CST + && (!op2_def || !is_gimple_assign (op2_def) + || !has_single_use (op2) + || gimple_assign_rhs_code (op2_def) != BIT_NOT_EXPR)) + op1 = expand_not_bitwise_binary (type, op1, op1_def); + else + op2 = expand_not_bitwise_binary (type, op2, op2_def); + } + /* Transform ~(X | Y) -> ~X & Y, or ~(X & Y) -> ~X | ~Y. */ + else + { + op1 = expand_not_bitwise_binary (type, op1, op1_def); + op2 = expand_not_bitwise_binary (type, op2, op2_def); + inner_code = (inner_code == BIT_AND_EXPR ? BIT_IOR_EXPR + : BIT_AND_EXPR); + } + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, inner_code, op1, op2); + update_stmt (gsi_stmt (gsi)); + remove_stmt_chain (old_op1); + return true; + } + + return false; +} + /* If CURR and LAST are a pair of ops that OPCODE allows us to eliminate through equivalences, do so, remove them from OPS, and return true. Otherwise, return false. */ @@ -2076,6 +2339,49 @@ remove_visited_stmt_chain (tree var) } } +/* Remove def stmt of VAR if VAR has zero uses and recurse + on rhs1, rhs2, and rhs3 operand if so. */ + +static void +remove_stmt_chain (tree var) +{ + gimple stmt; + gimple_stmt_iterator gsi; + tree var2, var3; + + while (1) + { + if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var)) + return; + stmt = SSA_NAME_DEF_STMT (var); + if (!stmt || !is_gimple_assign (stmt)) + return; + var = gimple_assign_rhs1 (stmt); + var2 = var3 = NULL_TREE; + + switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))) + { + case GIMPLE_TERNARY_RHS: + var3 = gimple_assign_rhs3 (stmt); + /* Fall through. */ + case GIMPLE_BINARY_RHS: + var2 = gimple_assign_rhs2 (stmt); + break; + default: + break; + } + gsi = gsi_for_stmt (stmt); + gsi_remove (&gsi, true); + release_defs (stmt); + /* Recurse on optional second and third operand, + if those arguments are of kind SSA_NAME. */ + if (var2 && TREE_CODE (var2) == SSA_NAME) + remove_stmt_chain (var2); + if (var3 && TREE_CODE (var3) == SSA_NAME) + remove_stmt_chain (var3); + } +} + /* This function checks three consequtive operands in passed operands vector OPS starting from OPINDEX and swaps two operands if it is profitable for binary operation @@ -2777,6 +3083,14 @@ can_reassociate_p (tree op) we want to break up k = t - q, but we won't until we've transformed q = b - r, which won't be broken up until we transform b = c - d. + Break up logical-not expressions of bitwise boolean-typed and/or/xor + operations for being able to optimize wihin combined conditions. + ~(A | B) -> ~A | ~B + ~(A & B) -> ~A & ~B + ~(A ^ B) -> A ^ ~B (special case if B is a constant) + If A or B are comparisons or are bitwise-not statement, then sink bit-not + into expression, if it is a single-use statement. + En passant, clear the GIMPLE visited flag on every statement. */ static void @@ -2785,21 +3099,34 @@ break_up_expr_bb (basic_block bb) gimple_stmt_iterator gsi; basic_block son; - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) { gimple stmt = gsi_stmt (gsi); gimple_set_visited (stmt, false); - if (!is_gimple_assign (stmt) - || !can_reassociate_p (gimple_assign_lhs (stmt))) + if (!is_gimple_assign (stmt)) + { + gsi_next (&gsi); + continue; + } + if (break_up_bitwise_combined_stmt (stmt)) continue; + if (!can_reassociate_p (gimple_assign_lhs (stmt))) + { + gsi_next (&gsi); + continue; + } + /* Look for simple gimple subtract operations. */ if (gimple_assign_rhs_code (stmt) == MINUS_EXPR) { if (!can_reassociate_p (gimple_assign_rhs1 (stmt)) || !can_reassociate_p (gimple_assign_rhs2 (stmt))) - continue; + { + gsi_next (&gsi); + continue; + } /* Check for a subtract used only in an addition. If this is the case, transform it into add of a negate for better @@ -2811,6 +3138,8 @@ break_up_expr_bb (basic_block bb) else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR && can_reassociate_p (gimple_assign_rhs1 (stmt))) VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt)); + + gsi_next (&gsi); } for (son = first_dom_son (CDI_DOMINATORS, bb); son; Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-1.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-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); + int r2 = (a | d | c) | ~b; + return (~r1 | r2); +} + +/* { 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-not-2.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-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 & ~c & b; + int r2 = ~a | b | ~d; + return (~r1 | r2); +} + +/* { 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-not-3.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-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 & ~c & b; + int r2 = ~a | b | ~d; + return (r1 & ~r2); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ +