From patchwork Wed Sep 21 13:29:55 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 115787 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 E2339B6F8A for ; Wed, 21 Sep 2011 23:30:32 +1000 (EST) Received: (qmail 10161 invoked by alias); 21 Sep 2011 13:30:28 -0000 Received: (qmail 10138 invoked by uid 22791); 21 Sep 2011 13:30:22 -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-f48.google.com (HELO mail-vw0-f48.google.com) (209.85.212.48) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 21 Sep 2011 13:29:57 +0000 Received: by vws7 with SMTP id 7so2334016vws.21 for ; Wed, 21 Sep 2011 06:29:55 -0700 (PDT) MIME-Version: 1.0 Received: by 10.220.74.20 with SMTP id s20mr167788vcj.13.1316611795736; Wed, 21 Sep 2011 06:29:55 -0700 (PDT) Received: by 10.220.179.8 with HTTP; Wed, 21 Sep 2011 06:29:55 -0700 (PDT) In-Reply-To: References: Date: Wed, 21 Sep 2011 15:29:55 +0200 Message-ID: Subject: Re: [patch tree-optimization]: Improve reassociation pass for bitwise-operations From: Kai Tietz To: Michael Matz Cc: GCC Patches , 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 revised patch adds support to tree-ssa-reassoc for intial normalizing of bitwise operation. So the reassociation pass is able to have better folding result. Also it has a final denormalzing of bitwise-operations after reassociation pass is completed to restore optimized writing. This patch is a bit huge, but I see here no good point to split it into smaller pieces due the denormalization and normalization of bitwise-operation are bound pretty much to each other. I added some additional testcases to check also for the denormalization pass. Normalization transforms the following patterns: - ~ (X | Y) -> ~X & ~Y - ~ (X & Y) -> ~X | ~Y - ~ (X ^ Y) -> ~X ^ Y - ~ (X ^ CST) -> X ^ CST'; with CST'=~CST - ~ (X cmp Y) -> X cmp' Y; with cmp' = inverted comparison of cmp - ((X cmp Y) != 0) -> X cmp Y - ((X cmp Y) == 0) -> X cmp' Y; with cmp' = inverted comparison of cmp - ~ (~X) -> X - (X ! Y) != 0 -> (X != 0) | (Y != 0) - (X | Y) == 0 -> (X == 0) & (Y == 0) by this even more complex statments like produced for this code: 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); } getting in gimple transformed to (as pseudo code) return (a != 0 & c != 0 & b != 0 & a != 0 & b == 0 & d != 0); which can be optimized to fixed result of zero. The de-normalization pass transforms the following patterns - ~X & ~Y -> ~ (X | Y) - ~X & CST -> ~ (X | CST'); with CST'=~CST - ~X | ~Y -> ~ (X & Y) - ~X | CST -> ~ (X & CST'); with CST'=~CST - ~X ^ Y -> ~ (X ^ Y) - ~X ^ CST -> X ^ CST'; with CST'=~CST - (X != 0) | (Y != 0) -> (X ! Y) != 0 - (X == 0) & (Y == 0) -> (X | Y) == 0 - (X != ~0) | (Y != ~0) -> (X & Y) != ~0 - (X == ~0) & (Y == ~0) -> (X & Y) != ~0 ChangeLog 2011-09-21 Kai Tietz * tree-ssa-reassoc.c (gimple build_and_add_sum): Add forwarder declaration and add support for unary-expressions. (remove_visited_stmt_chain): Add forwarder declaration. (push_bitwise_op): New helper function. (remove_bitwise_op): Likewise. (operate_bitwise_stmt): Likewise. (repropagate_bitwise): Likewise. (operate_bitwise_xor_stmt): Likewise. (make_new_tmp_statement): Likewise. (expand_not_bitwise_binary): Likewise. (get_bitwise_single_use_root): Likewise. (is_bitwise_not): Likewise. (walk_bitwise_stmt_elems): Likewise. (expand_cmp_ior): Likewise. (rebuild_vector_tree): Likewise. (break_up_bitwise_combined_stmt): Likewise. (merge_bitwise_compares): Likewise. (bitwise_ops): New static variable. (break_up_subtract_bb): Renamed to break_up_expr_bb and add call to break_up_bitwise_combined_stmt function. (do_reassoc): Rename break_up_subtract_bb call as break_up_expr_bb. (init_reassoc): Initialize bitwise_ops vector. (fini_reassoc): Destroy bitwise_ops vector. (execute_reassoc): Add call for repropagate_bitwise function. ChangeLog gcc/testsuite 2011-09-21 Kai Tietz * gcc.dg/tree-ssa/reassoc-26.c: New test. * gcc.dg/tree-ssa/reassoc-27.c: New test. * gcc.dg/tree-ssa/reassoc-28.c: New test. * gcc.dg/tree-ssa/reassoc-29.c: New test. * gcc.dg/tree-ssa/reassoc-30.c: New test. * gcc.dg/tree-ssa/reassoc-31.c: New test. * gcc.dg/tree-ssa/reassoc-32.c: New test. * gcc.dg/tree-ssa/reassoc-33.c: New test. * gcc.dg/tree-ssa/reassoc-34.c: New test. * gcc.dg/tree-ssa/reassoc-35.c: New test. Bootstrapped and regression tested for all languages (including Ada and Obj-C++) on host 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 @@ -43,6 +43,10 @@ along with GCC; see the file COPYING3. #include "target.h" #include "params.h" +/* Forwarders. */ +static gimple build_and_add_sum (tree, tree, tree, enum tree_code); +static void remove_visited_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 than we do, in different orders, etc). @@ -50,7 +54,9 @@ along with GCC; see the file COPYING3. It consists of five steps: 1. Breaking up subtract operations into addition + negate, where - it would promote the reassociation of adds. + it would promote the reassociation of adds. Additionally 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. @@ -194,7 +200,9 @@ static struct pointer_map_t *operand_ran /* Forward decls. */ static long get_rank (tree); - +static void push_bitwise_op (tree); +static void remove_bitwise_op (tree); +static void operate_bitwise_stmt (gimple, enum tree_code); /* Bias amount for loop-carried phis. We want this to be larger than the depth of any reassociation tree we can see, but not larger than @@ -556,6 +564,385 @@ get_unary_op (tree name, enum tree_code return NULL_TREE; } +/* Create a temorary 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 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); +} + +/* Perfrom on tree LHS with optional definition statement EPXR + a logic-not operation. TYPE is of kind boolean with a 1-bit + precision. */ +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); + } + else if (code == BIT_NOT_EXPR) + op1 = gimple_assign_rhs1 (expr); + else + return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs, NULL_TREE, expr); + + /* ~(~X) -> X. */ + if (code == BIT_NOT_EXPR) + return op1; + + /* Invert comparison if possible, otherwise fall through to + default case. */ + else 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); + } + /* ~(A & B) -> ~A | ~B. */ + else if (code == BIT_AND_EXPR) + { + if (TREE_CODE (op1) != SSA_NAME + || !(s1 = SSA_NAME_DEF_STMT (op1)) + || !is_gimple_assign (s1) + || !has_single_use (op1)) + s1 = NULL; + 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); + if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2)) + { + remove_visited_stmt_chain (op2); + return op1; + } + else if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2)) + { + remove_visited_stmt_chain (op1); + return op2; + } + return make_new_tmp_statement (type, BIT_IOR_EXPR, op1, op2, expr); + } + /* ~(A | B) -> ~A & ~B. */ + else if (code == BIT_IOR_EXPR) + { + if (TREE_CODE (op1) != SSA_NAME + || !(s1 = SSA_NAME_DEF_STMT (op1)) + || !is_gimple_assign (s1) + || !has_single_use (op1)) + s1 = NULL; + if (TREE_CODE (op2) != SSA_NAME + || !(s2 = SSA_NAME_DEF_STMT (op2)) + || !is_gimple_assign (s2) + || !has_single_use (op2)) + s2 = NULL; + op1 = expand_not_bitwise_binary (type, op1, s1); + op2 = expand_not_bitwise_binary (type, op2, s2); + if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2)) + { + remove_visited_stmt_chain (op1); + return op2; + } + else if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2)) + { + remove_visited_stmt_chain (op2); + return op1; + } + return make_new_tmp_statement (type, BIT_AND_EXPR, 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) + { + if (TREE_CODE (op1) != SSA_NAME + || !(s1 = SSA_NAME_DEF_STMT (op1)) + || !is_gimple_assign (s1) + || !has_single_use (op1)) + s1 = NULL; + if (TREE_CODE (op2) != SSA_NAME + || !(s2 = SSA_NAME_DEF_STMT (op2)) + || !is_gimple_assign (s2) + || !has_single_use (op2)) + s2 = NULL; + 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)) + { + remove_visited_stmt_chain (op2); + return op1; + } + + if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2)) + { + remove_visited_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); + } + + if (!types_compatible_p (type, TREE_TYPE (lhs))) + abort (); + + /* Default case lhs -> ~lhs */ + return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs, + NULL_TREE, expr); +} + +/* Helper routine to expand X CODE 0. + Cases are + (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 CODE variable can be either NE_EXPR, or EQ_EXPR. It indicates + what 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; + + 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 (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); + + 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); + + 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); + } + 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 statement STMT if it is a combined expressions made out of + bitwise operations. Handle expansion of (A | B) !=/== 0, and ~(A op B). */ +static bool +break_up_bitwise_combined_stmt (gimple stmt) +{ + tree op1, op2, old_op; + 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_op = op1; + op2 = NULL_TREE; + + if (code == EQ_EXPR || code == NE_EXPR) + op2 = gimple_assign_rhs2 (stmt); + + /* Check that left-hand operand is a gimple-assignment + and has single use. */ + if ((code != BIT_NOT_EXPR + && code != EQ_EXPR && code != NE_EXPR) + || TREE_CODE (op1) != SSA_NAME) + return false; + op1_def = SSA_NAME_DEF_STMT (op1); + if (!op1_def + || !is_gimple_assign (op1_def) + || !has_single_use (op1)) + return false; + + 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); + + remove_bitwise_op (old_op); + + 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_visited_stmt_chain (old_op); + push_bitwise_op (gimple_assign_lhs (stmt)); + 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); + + 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_visited_stmt_chain (old_op); + push_bitwise_op (gimple_assign_lhs (stmt)); + 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_visited_stmt_chain (old_op); + 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) toX ^ 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_visited_stmt_chain (old_op); + push_bitwise_op (gimple_assign_lhs (stmt)); + 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. */ @@ -632,6 +1019,7 @@ eliminate_duplicate_pair (enum tree_code } static VEC(tree, heap) *plus_negates; +static VEC(tree, heap) *bitwise_ops; /* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not expression, look in OPS for a corresponding positive operation to cancel @@ -1017,8 +1405,8 @@ zero_one_operation (tree *def, enum tree while (1); } -/* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for - the result. Places the statement after the definition of either +/* Builds one statement performing OP1 OPCODE OP2, OPCODE op1 using TMPVAR + for the result. Places the statement after the definition of either OP1 or OP2. Returns the new statement. */ static gimple @@ -1037,7 +1425,7 @@ build_and_add_sum (tree tmpvar, tree op1 /* Find an insertion place and insert. */ if (TREE_CODE (op1) == SSA_NAME) op1def = SSA_NAME_DEF_STMT (op1); - if (TREE_CODE (op2) == SSA_NAME) + if (op2 && TREE_CODE (op2) == SSA_NAME) op2def = SSA_NAME_DEF_STMT (op2); if ((!op1def || gimple_nop_p (op1def)) && (!op2def || gimple_nop_p (op2def))) @@ -2204,6 +2592,758 @@ linearize_expr_tree (VEC(operand_entry_t add_to_ops_vec (ops, binrhs); } +/* This function seeks the root assignment-statement of LHS, which + is a bitwise-wise expression. It additional don't walk over + none-single-use elements. */ +static tree +get_bitwise_single_use_root (tree lhs) +{ + gimple user; + if (TREE_CODE (lhs) != SSA_NAME + || !SSA_NAME_DEF_STMT (lhs) + || !is_gimple_assign (SSA_NAME_DEF_STMT (lhs)) + || !has_single_use (lhs)) + return lhs; + user = get_single_immediate_use (lhs); + if (!user) + return lhs; + do + { + if (!is_gimple_assign (user)) + return lhs; + switch (gimple_assign_rhs_code (user)) + { + case BIT_NOT_EXPR: + case BIT_XOR_EXPR: + case BIT_AND_EXPR: + case BIT_IOR_EXPR: + break; + default: + return lhs; + } + lhs = gimple_assign_lhs (user); + } + while ((user = get_single_immediate_use (lhs)) != NULL); + + return lhs; +} + +/* Saves LHS on vector BITWISE_OPS, if it isn't + already stored in vector BITWISE_OPS. */ +static void +push_bitwise_op (tree lhs) +{ + gimple user; + + /* Check if we are on a root-element. */ + if (has_single_use (lhs) + && (user = get_single_immediate_use (lhs)) != NULL + && is_gimple_assign (user)) + { + enum tree_code ucode = gimple_assign_rhs_code (user); + if (ucode == BIT_AND_EXPR + || ucode == BIT_IOR_EXPR + || ucode == BIT_XOR_EXPR + || ucode == BIT_NOT_EXPR) + return; + } + /* Find root element. */ + lhs = get_bitwise_single_use_root (lhs); + + /* Check that LHS is unique in vector BITWISE_OPS. */ + if (bitwise_ops != NULL) + { + unsigned int i = 0; + tree x; + + FOR_EACH_VEC_ELT (tree, bitwise_ops, i, x) + { + if (x == lhs) + return; + } + } + + VEC_safe_push (tree, heap, bitwise_ops, lhs); +} + +/* Function removes element LHS from vector + BITWISE_OPS. */ +static void +remove_bitwise_op (tree lhs) +{ + /* Check that LHS is unique in vector BITWISE_OPS. */ + if (bitwise_ops != NULL) + { + unsigned int i = 0; + tree x; + + FOR_EACH_VEC_ELT (tree, bitwise_ops, i, x) + { + if (x == lhs) + { + VEC_ordered_remove (tree, bitwise_ops, i); + return; + } + } + } +} + +/* This routine returns TRUE, if LHS is assignment with + tree-code BIT_NOT_EXPR. Otherwise it returns FALSE. */ + +static bool +is_bitwise_not (tree lhs) +{ + gimple stmt; + + if (TREE_CODE (lhs) != SSA_NAME) + return false; + stmt = SSA_NAME_DEF_STMT (lhs); + if (!stmt + || !is_gimple_assign (stmt)) + return false; + + return gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR; +} + +/* Helper function to sort statements starting from STMT with tree-code + CODE into ORG for none-not-expressions, into NOT for not-expressions, + into VCMP Y == 0 for CODE equal to bitwise-or, into VCMP Y != 0 for + CODE eual to bitwise-and, and into CST for integral constants. */ +static void +walk_bitwise_stmt_elems (gimple stmt, enum tree_code code, + VEC(tree, heap) **vcst, + VEC(tree, heap) **vnot, + VEC(tree, heap) **vcmp_zero, + VEC(tree, heap) **vcmp_m1, + VEC(tree, heap) **vexpr) +{ + gimple s; + tree l; + + l = gimple_assign_rhs1 (stmt); + if (TREE_CODE (l) == INTEGER_CST) + VEC_safe_push (tree, heap, *vcst, l); + else if (TREE_CODE (l) != SSA_NAME + || (s = SSA_NAME_DEF_STMT (l)) == NULL + || !is_gimple_assign (s) + || !has_single_use (l)) + VEC_safe_push (tree, heap, *vexpr, l); + else if (gimple_assign_rhs_code (s) == code) + walk_bitwise_stmt_elems (s, code, vcst, vnot, vcmp_zero, vcmp_m1, vexpr); + else if (is_bitwise_not (l)) + VEC_safe_push (tree, heap, *vnot, l); + /* (A == 0) & (B == 0) -> (A | B) == 0 + (A != 0) | (B != 0) -> (A | B) != 0. */ + else if (((code == BIT_AND_EXPR + && gimple_assign_rhs_code (s) == EQ_EXPR) + || (code == BIT_IOR_EXPR + && gimple_assign_rhs_code (s) == NE_EXPR)) + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s))) + && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST + && integer_zerop (gimple_assign_rhs2 (s))) + VEC_safe_push (tree, heap, *vcmp_zero, l); + /* (A == -1) & (B == -1) -> (A & B) == -1 + (A != -1) | (B != -1) -> (A & B) != -1 */ + else if (((code == BIT_AND_EXPR + && gimple_assign_rhs_code (s) == EQ_EXPR) + || (code == BIT_IOR_EXPR + && gimple_assign_rhs_code (s) == NE_EXPR)) + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s))) + && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST + && integer_all_onesp (gimple_assign_rhs2 (s))) + VEC_safe_push (tree, heap, *vcmp_m1, l); + else + { + switch (gimple_assign_rhs_code (s)) + { + case BIT_IOR_EXPR: + case BIT_AND_EXPR: + case BIT_XOR_EXPR: + operate_bitwise_stmt (s, gimple_assign_rhs_code (s)); + break; + default: + break; + } + + VEC_safe_push (tree, heap, *vexpr, l); + } + + l = gimple_assign_rhs2 (stmt); + + if (TREE_CODE (l) == INTEGER_CST) + { + VEC_safe_push (tree, heap, *vcst, l); + return; + } + if (TREE_CODE (l) != SSA_NAME + || (s = SSA_NAME_DEF_STMT (l)) == NULL + || !is_gimple_assign (s) + || !has_single_use (l)) + VEC_safe_push (tree, heap, *vexpr, l); + else if (gimple_assign_rhs_code (s) == code) + walk_bitwise_stmt_elems (s, code, vcst, vnot, vcmp_zero, vcmp_m1, vexpr); + else if (is_bitwise_not (l)) + VEC_safe_push (tree, heap, *vnot, l); + /* (A == 0) & (B == 0) -> (A | B) == 0 + (A != 0) | (B != 0) -> (A | B) != 0. */ + else if (((code == BIT_AND_EXPR + && gimple_assign_rhs_code (s) == EQ_EXPR) + || (code == BIT_IOR_EXPR + && gimple_assign_rhs_code (s) == NE_EXPR)) + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s))) + && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST + && integer_zerop (gimple_assign_rhs2 (s))) + VEC_safe_push (tree, heap, *vcmp_zero, l); + /* (A == -1) & (B == -1) -> (A & B) == -1 + (A != -1) | (B != -1) -> (A & B) != -1 */ + else if (((code == BIT_AND_EXPR + && gimple_assign_rhs_code (s) == EQ_EXPR) + || (code == BIT_IOR_EXPR + && gimple_assign_rhs_code (s) == NE_EXPR)) + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (s))) + && TREE_CODE (gimple_assign_rhs2 (s)) == INTEGER_CST + && integer_all_onesp (gimple_assign_rhs2 (s))) + VEC_safe_push (tree, heap, *vcmp_m1, l); + else + { + switch (gimple_assign_rhs_code (s)) + { + case BIT_IOR_EXPR: + case BIT_AND_EXPR: + case BIT_XOR_EXPR: + operate_bitwise_stmt (s, gimple_assign_rhs_code (s)); + break; + default: + break; + } + + VEC_safe_push (tree, heap, *vexpr, l); + } +} + +/* Helper function to rebuild a binary tree of CODE elements + from vector VEC. + If LASTP is NULL, then all elements + are combined and result is returned, otherwise the last + element of vector VEC is stored in LASTP and all - but the last - + elements are merged and returned. + Note: for vector with just one element, this element is returned + and LASTP is set to NULL, if provided. + If INNER_LEFT is true, the RHS1 operand of VEC element + is used, otherwise the VEC element itself is used. */ +static tree +rebuild_vector_tree (VEC(tree, heap) *vec, + enum tree_code code, tree *lastp, bool inner_left) +{ + gimple s; + unsigned int i = 0; + tree r = NULL_TREE, x, r2 = NULL_TREE; + + FOR_EACH_VEC_ELT (tree, vec, i, x) + { + s = SSA_NAME_DEF_STMT (x); + + if (inner_left) + x = gimple_assign_rhs1 (s); + if (!r) + r = x; + else if (!r2) + r2 = x; + else + { + r = make_new_tmp_statement (TREE_TYPE (r), code, r, r2, s); + r2 = x; + } + } + if (lastp) + *lastp = r2; + else if (r && r2) + { + s = SSA_NAME_DEF_STMT (r); + r = make_new_tmp_statement (TREE_TYPE (r), code, r, r2, s); + } + return r; +} + +/* Sink not-expression out of xor-expression-sequences TCST, NOT, and ORG + generated from STMT. + Returns TRUE, if statement STMT was modified, otherwise FALSE. */ +static bool +operate_bitwise_xor_stmt (gimple stmt, tree tcst, VEC(tree, heap) *vnot, + VEC(tree, heap) *vexpr) +{ + gimple_stmt_iterator gsi; + unsigned int i = VEC_length (tree, vnot); + tree l = NULL_TREE, r = NULL_TREE; + bool inv = false; + + /* If the amount of not-expressions is odd, then we have two cases: + a) we have a constant, so we can sink one not into integeral constant + as ~X ^ CST -> X ^ CST' with CST' = ~CST. + b) we need to add to the hole statment a bitwise-not expression. */ + if ((i & 1) != 0) + { + if (tcst) + { + tcst = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (tcst), tcst); + /* See if we can eleminate constant. */ + if (integer_zerop (tcst)) + tcst = NULL; + } + else + inv = true; + } + + if (vnot && vexpr) + { + l = rebuild_vector_tree (vnot, BIT_XOR_EXPR, NULL, true); + r = rebuild_vector_tree (vexpr, BIT_XOR_EXPR, NULL, false); + if (tcst) + { + l = make_new_tmp_statement (TREE_TYPE (l), BIT_XOR_EXPR, l, r, stmt); + r = tcst; + } + } + else if (vnot) + { + l = rebuild_vector_tree (vnot, BIT_XOR_EXPR, &r, true); + if (tcst) + { + if (!r) + r = tcst; + else + { + l = make_new_tmp_statement (TREE_TYPE (l), BIT_XOR_EXPR, l, r, stmt); + r = tcst; + } + } + } + else if (tcst) + { + l = rebuild_vector_tree (vexpr, BIT_XOR_EXPR, NULL, false); + if (l) + r = tcst; + else + { + l = tcst; + r = NULL_TREE; + } + } + else + l = rebuild_vector_tree (vexpr, BIT_XOR_EXPR, &r, false); + + if (inv) + { + if (r) + l = make_new_tmp_statement (TREE_TYPE (l), BIT_XOR_EXPR, l, r, stmt); + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, BIT_NOT_EXPR, l, NULL_TREE); + } + else + { + gsi = gsi_for_stmt (stmt); + if (r) + gimple_assign_set_rhs_with_ops (&gsi, BIT_XOR_EXPR, l, r); + else + gimple_assign_set_rhs_from_tree (&gsi, l); + } + update_stmt (gsi_stmt (gsi));; + return true; +} + +/* Helper function to merge:compares + If IS_IOR is TRUE. then merge VCMP elements + - (X != 0) | (Y != 0) -> (X | Y) != 0 + - (X == 0) & (Y == 0) -> (X | Y) == 0. + + If IS_IOR is FALSE. then merge VCMP elements + - (X != ~0) | (Y != ~0) -> (X & Y) != ~0 + - (X == ~0) & (Y == ~0) -> (X & Y) == ~0. + + CODE specifies the final compare expression code. It can be either + EQ_EXPR, or NE_EXPR. + + If DESTSTMT is not NULL, then final compare instruction + gets assigned to it, otherwise an new temporary is used + and stored in VEXPR vector. + + Special note: We try to merge first elements of compatible + types, before doing final merge by casting up to widest type. */ +static void +merge_bitwise_compares (VEC(tree, heap) **vcmp, VEC(tree, heap) **vexpr, + enum tree_code code, gimple deststmt, bool is_ior) +{ + unsigned int i; + unsigned int len = VEC_length (tree, *vcmp); + tree l, r, x, cmp_type = NULL_TREE; + VEC(tree, heap) *vtmp = NULL; + enum tree_code cmp_code; + + /* If we have just one compare-element, then simply + move it to ORG vector and return. */ + if (len <= 1) + { + FOR_EACH_VEC_ELT (tree, *vcmp, i, x) + { + VEC_safe_push (tree, heap, *vexpr, x); + VEC_ordered_remove (tree, *vcmp, i); + } + + VEC_free (tree, heap, *vcmp); + *vcmp = NULL; + return; + } + + /* First merge all elements with compatible type, and move + intermediate result into VTMP vector. */ + while (VEC_length (tree, *vcmp) > 0) + { + cmp_type = NULL_TREE; + l = NULL_TREE; + for (i = 0; VEC_iterate (tree, (*vcmp), (i), (x));) + { + gimple s = SSA_NAME_DEF_STMT (x); + r = gimple_assign_rhs1 (s); + if (!l) + { + l = r; + cmp_type = TREE_TYPE (x); + VEC_ordered_remove (tree, *vcmp, i); + } + else if (types_compatible_p (TREE_TYPE (r), TREE_TYPE (l))) + { + l = make_new_tmp_statement (TREE_TYPE (l), + (is_ior ? BIT_IOR_EXPR + : BIT_AND_EXPR), l, r, s); + VEC_ordered_remove (tree, *vcmp, i); + } + else + ++i; + } + VEC_safe_push (tree, heap, vtmp, l); + } + VEC_free (tree, heap, *vcmp); + *vcmp = NULL; + + /* Now do final merge of all elements in VTMP vector by casting to + wider-type. */ + l = NULL_TREE; + r = NULL_TREE; + FOR_EACH_VEC_ELT (tree, vtmp, i, x) + { + tree type; + type = TREE_TYPE (x); + + /* If we handle (X & Y) ==/!= ~0 case, we need + to work on signed types. */ + if (!is_ior && TYPE_UNSIGNED (type) && VEC_length (vtmp) > 1) + { + type = signed_type_for (type); + x = make_new_tmp_statement (type, NOP_EXPR, x, NULL_TREE, SSA_NAME_DEF_STMT (x)); + } + if (!l) + { + l = x; + r = type; + } + else + { + if (TYPE_PRECISION (r) < TYPE_PRECISION (type)) + { + l = make_new_tmp_statement (type, NOP_EXPR, l, NULL_TREE, SSA_NAME_DEF_STMT (x)); + r = type; + } + else if (TYPE_PRECISION (r) > TYPE_PRECISION (type) + || !types_compatible_p (r, type)) + x = make_new_tmp_statement (r, NOP_EXPR, x, NULL_TREE, SSA_NAME_DEF_STMT (x)); + l = make_new_tmp_statement (r, (is_ior ? BIT_IOR_EXPR + : BIT_AND_EXPR), + l, x, SSA_NAME_DEF_STMT (x)); + } + } + + /* Generate final L != 0, or L == 0 to statement. + a) (X == 0) & (Y == 0) -> (X | Y) == 0 + b) (X != 0) | (Y != 0) -> (X | Y) != 0 + c) (X == -1) & (Y == -1) -> (X & Y) == -1 + d) (X != -1) | (Y != -1) -> (X & Y) != -1 + */ + cmp_code = (code == BIT_AND_EXPR ? EQ_EXPR : NE_EXPR); + if (!deststmt) + { + tree cst_val = build_zero_cst (TREE_TYPE (l)); + + if (!is_ior) + cst_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (l), cst_val); + l = make_new_tmp_statement (cmp_type, + cmp_code, l, + cst_val, + SSA_NAME_DEF_STMT (l)); + VEC_safe_push (tree, heap, *vexpr, l); + } + else + { + gimple_stmt_iterator gsi; + tree cst_val = build_zero_cst (TREE_TYPE (l)); + + if (!is_ior) + cst_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (l), cst_val); + + gsi = gsi_for_stmt (deststmt); + gimple_assign_set_rhs_with_ops (&gsi, cmp_code, l, + cst_val); + update_stmt (deststmt); + } + VEC_free (tree, heap, vtmp); +} + +/* Sink bitwise-not expression out of bitwise-binary sequence for STMT. The + tree-code of the statement-sequence CODE. + Following patterns are used for transformations: + ~X and ~Y -> ~(X or Y) + ~X or ~Y -> ~(X and Y) + ~X xor ~Y -> X xor Y + ~X xor Y -> ~(X xor Y) + ~X xor CST -> X xor CST' (with CST' = ~CST). + (X == 0) and (Y == 0) -> (X | Y) == 0, if X and Y have + integral types. + (X == -1) and (Y == -1) -> (X & Y) == -1, if X and Y have + integral types. + (X != 0) or (Y != 0) -> (X | Y) != 0, if X and Y have + integral types. + (X != -1) or (Y != -1) -> (X & Y) != -1, if X and Y have + integral types. + + */ +static void +operate_bitwise_stmt (gimple stmt, enum tree_code code) +{ + unsigned int i = 0; + tree x, tcst = NULL_TREE; + tree tnot = NULL_TREE, torg = NULL_TREE; + tree l, r; + gimple_stmt_iterator gsi; + VEC(tree, heap) *vcst = NULL; + VEC(tree, heap) *vnot = NULL; + VEC(tree, heap) *vcmp_zero = NULL; + VEC(tree, heap) *vcmp_m1 = NULL; + VEC(tree, heap) *vexpr = NULL; + enum tree_code icode; + bool do_repropagate = false; + + if (gimple_assign_rhs_code (stmt) != code) + abort (); + + walk_bitwise_stmt_elems (stmt, code, &vcst, &vnot, + &vcmp_zero, &vcmp_m1, &vexpr); + + /* There are constants, */ + if (VEC_length (tree, vcst) > 1) + do_repropagate = true; + /* There are comparisons-to-zero, */ + else if (VEC_length (tree, vcmp_zero) > 1 + || VEC_length (tree, vcmp_m1) > 1) + do_repropagate = true; + /* There are not-expressions, */ + else if (VEC_length (tree, vnot) > 1) + do_repropagate = true; + /* If we have (~X & CST), we convert to ~(X | CST') with CST'=~CST. + If we have (~X | CST), we convert to ~(X & CST') with CST'=~CST. */ + else if (VEC_length (tree, vnot) == 1 + && VEC_length (tree, vexpr) == 0 + && VEC_length (tree, vcmp_zero) == 0 + && VEC_length (tree, vcmp_m1) == 0 + && VEC_length (tree, vcst) >= 1) + do_repropagate = true; + /* For xor-expressions we do following conversion: + a) (~X ^ CST) -> X ^ CST'; with CST'=~CST. + b) (~X ^ Y) -> ~(X ^ Y). */ + else if (code == BIT_XOR_EXPR + && VEC_length (tree, vnot) == 1) + do_repropagate = true; + + if (!do_repropagate) + { + VEC_free (tree, heap, vcst); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vcmp_zero); + VEC_free (tree, heap, vcmp_m1); + VEC_free (tree, heap, vexpr); + return; + } + + l = gimple_assign_rhs1 (stmt); + r = gimple_assign_rhs2 (stmt); + + /* First combine integral constant bitwise operations. */ + FOR_EACH_VEC_ELT (tree, vcst, i, x) + { + if (!tcst) + tcst = x; + else + tcst = fold_build2 (code, TREE_TYPE (x), tcst, x); + } + VEC_free (tree, heap, vcst); + vcst = NULL; + + /* Do we have only vcmp_zero elements, then directly assign result + of combine to final stmt. */ + if (!tcst && !vexpr && !vnot && !vcmp_m1) + { + merge_bitwise_compares (&vcmp_zero, &vexpr, code, stmt, true); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + return; + } + /* Do we have only vcmp_m1 elements, then directly assign result + of combine to final stmt. */ + if (!tcst && !vexpr && !vnot && !vcmp_zero) + { + merge_bitwise_compares (&vcmp_m1, &vexpr, code, stmt, false); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + return; + } + + merge_bitwise_compares (&vcmp_zero, &vexpr, code, NULL, true); + merge_bitwise_compares (&vcmp_m1, &vexpr, code, NULL, false); + + /* If we deal only with constants, assign + calculated constant. */ + if (tcst && !vnot && !vexpr) + { + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_from_tree (&gsi, tcst); + update_stmt (gsi_stmt (gsi)); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + return; + } + + if (code == BIT_XOR_EXPR) + { + operate_bitwise_xor_stmt (stmt, tcst, vnot, vexpr); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return; + } + + /* See if we can eleminate constant. */ + if (tcst + && ((code == BIT_AND_EXPR && integer_all_onesp (tcst)) + || (code == BIT_IOR_EXPR && integer_zerop (tcst)))) + tcst = NULL; + + /* Propagate bitwise and/or statements. */ + + /* Inverse for binary and/or. */ + icode = (code == BIT_IOR_EXPR ? BIT_AND_EXPR : BIT_IOR_EXPR); + + /* Build inverse tree for bitwise-not part. */ + if (VEC_length (tree, vnot) > 0) + { + tnot = rebuild_vector_tree (vnot, icode, NULL, true); + torg = rebuild_vector_tree (vexpr, code, NULL, false); + if (tnot && !tcst && !torg) + { + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, BIT_NOT_EXPR, tnot, NULL_TREE); + update_stmt (gsi_stmt (gsi)); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return; + } + if (!tnot) + abort (); + tnot = make_new_tmp_statement (TREE_TYPE (tnot), BIT_NOT_EXPR, tnot, + NULL_TREE, SSA_NAME_DEF_STMT (tnot)); + if (torg) + { + if (!tcst) + { + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, code, tnot, torg); + update_stmt (gsi_stmt (gsi)); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return; + } + tnot = make_new_tmp_statement (TREE_TYPE (tnot), code, tnot, torg, + SSA_NAME_DEF_STMT (tnot)); + } + gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_with_ops (&gsi, code, tnot, tcst); + update_stmt (gsi_stmt (gsi)); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return; + } + if (!tcst) + torg = rebuild_vector_tree (vexpr, code, &tcst, false); + else + torg = rebuild_vector_tree (vexpr, code, NULL, false); + gsi = gsi_for_stmt (stmt); + if (tcst) + gimple_assign_set_rhs_with_ops (&gsi, code, torg, tcst); + else + gimple_assign_set_rhs_from_tree (&gsi, torg); + update_stmt (gsi_stmt (gsi)); + remove_visited_stmt_chain (l); + remove_visited_stmt_chain (r); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); +} + +/* Repropagate bitwise-operations back to de-normalized from. + ~X op ~Y -> ~(X op' Y). */ +static void +repropagate_bitwise (void) +{ + unsigned int i = 0; + tree x; + gimple user; + enum tree_code ucode; + + FOR_EACH_VEC_ELT (tree, bitwise_ops, i, x) + { + gimple stmt; + enum tree_code code; + + if (TREE_CODE (x) != SSA_NAME) + continue; + stmt = SSA_NAME_DEF_STMT (x); + if (!stmt || !is_gimple_assign (stmt)) + continue; + code = gimple_assign_rhs_code (stmt); + if (code == BIT_NOT_EXPR) + continue; + if (code != BIT_XOR_EXPR && code != BIT_IOR_EXPR + && code != BIT_AND_EXPR) + continue; + /* Check if we are on a root-element. */ + if (has_single_use (x) + && (user = get_single_immediate_use (x)) != NULL + && is_gimple_assign (user)) + { + ucode = gimple_assign_rhs_code (user); + if (ucode == BIT_AND_EXPR + || ucode == BIT_IOR_EXPR + || ucode == BIT_XOR_EXPR) + continue; + } + operate_bitwise_stmt (stmt, code); + } +} + /* Repropagate the negates back into subtracts, since no other pass currently does it. */ @@ -2320,29 +3460,65 @@ 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 comparison !=/== 0 operations of bitwise-or operations for + being able to optimize within combined conditions. + (A | B) != 0 -> (A != 0) || (B != 0) + (A | B) == 0 -> (A == 0) && (B != 0) + + 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) + En passant, clear the GIMPLE visited flag on every statement. */ static void -break_up_subtract_bb (basic_block bb) +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; + switch (gimple_assign_rhs_code (stmt)) + { + case BIT_AND_EXPR: + case BIT_IOR_EXPR: + case BIT_XOR_EXPR: + /* We might want to remember this statement + for repropagation. */ + push_bitwise_op (gimple_assign_lhs (stmt)); + break; + default: + break; + } + + 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 @@ -2354,11 +3530,12 @@ break_up_subtract_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; son = next_dom_son (CDI_DOMINATORS, son)) - break_up_subtract_bb (son); + break_up_expr_bb (son); } /* Reassociate expressions in basic block BB and its post-dominator as @@ -2524,7 +3701,8 @@ debug_ops_vector (VEC (operand_entry_t, static void do_reassoc (void) { - break_up_subtract_bb (ENTRY_BLOCK_PTR); + break_up_expr_bb (ENTRY_BLOCK_PTR); + reassociate_bb (EXIT_BLOCK_PTR); } @@ -2581,6 +3759,7 @@ init_reassoc (void) free (bbs); calculate_dominance_info (CDI_POST_DOMINATORS); plus_negates = NULL; + bitwise_ops = NULL; } /* Cleanup after the reassociation pass, and print stats if @@ -2602,6 +3781,7 @@ fini_reassoc (void) free_alloc_pool (operand_entry_pool); free (bb_rank); VEC_free (tree, heap, plus_negates); + VEC_free (tree, heap, bitwise_ops); free_dominance_info (CDI_POST_DOMINATORS); loop_optimizer_finalize (); } @@ -2615,6 +3795,7 @@ execute_reassoc (void) do_reassoc (); repropagate_negates (); + repropagate_bitwise (); fini_reassoc (); return 0; Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-30.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-30.c @@ -0,0 +1,12 @@ +/* { 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" } } */ Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-31.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-31.c @@ -0,0 +1,12 @@ +/* { 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-26.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-26.c @@ -0,0 +1,12 @@ +/* { 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-27.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-27.c @@ -0,0 +1,12 @@ +/* { 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" } } */ Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c @@ -0,0 +1,12 @@ +/* { 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-29.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-29.c @@ -0,0 +1,12 @@ +/* { 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-32.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, int b, int c, int d) +{ + return (~a & ~b) ^ (~c | ~d); +} + +int foo2 (int a, int b, int c, int d) +{ + return (~a & ~b & ~c & ~d) ^ 0xff; +} + +int foo3 (int a, int b, int c, int d) +{ + return ~a ^ b ^ ~c ^ ~d ^ 0xff; +} + +int foo4 (int a, int b, int c, int d) +{ + return ~a ^ ~b ^ ~c ^ ~d; +} + +/* { dg-final { scan-tree-dump-times " ~" 0 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, int b, int c, int d) +{ + int r = (a == -1) & (b == -1); + int q = (c == -1) & (d == -1); + return r & q; +} + +int bar (int a, int b, int c, int d) +{ + int r = (a != -1) | (b != -1); + int q = (c != -1) | (d != -1); + return r | q; +} + +/* { dg-final { scan-tree-dump-times " == -1" 2 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, char b, short c, long d) +{ + int r = (a == -1) & (b == -1); + int q = (c == -1) & (d == -1); + return r & q; +} + +int bar (int a, char b, short c, long d) +{ + int r = (a != -1) | (b != -1); + int q = (c != -1) | (d != -1); + return r | q; +} + +/* { dg-final { scan-tree-dump-times " == -1" 2 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c =================================================================== --- /dev/null +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */ + +int foo (int a, unsigned char b, unsigned short c, unsigned long d) +{ + unsigned char b1 = ~0; + unsigned short c1 = ~0; + unsigned long d1 = ~0; + int r = (a == -1) & (b == b1); + int q = (c == c1) & (d == d1); + return r & q; +} + +int bar (int a, unsigned char b, unsigned short c, unsigned long d) +{ + unsigned char b1 = ~0; + unsigned short c1 = ~0; + unsigned long d1 = ~0; + int r = (a != -1) | (b != b1); + int q = (c != c1) | (d != d1); + return r | q; +} + +/* { dg-final { scan-tree-dump-times " == -1" 2 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */