From patchwork Tue Oct 4 12:17:15 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 117608 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 1829BB6F7E for ; Tue, 4 Oct 2011 23:17:40 +1100 (EST) Received: (qmail 22666 invoked by alias); 4 Oct 2011 12:17:36 -0000 Received: (qmail 22650 invoked by uid 22791); 4 Oct 2011 12:17:33 -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, TW_VT 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; Tue, 04 Oct 2011 12:17:15 +0000 Received: by mail-vx0-f175.google.com with SMTP id fl17so298726vcb.20 for ; Tue, 04 Oct 2011 05:17:15 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.19.162 with SMTP id g2mr1146508vde.44.1317730635068; Tue, 04 Oct 2011 05:17:15 -0700 (PDT) Received: by 10.220.180.5 with HTTP; Tue, 4 Oct 2011 05:17:15 -0700 (PDT) Date: Tue, 4 Oct 2011 14:17:15 +0200 Message-ID: Subject: [patch tree-optimization]: 2 of 2: Add denormalization of bitwise-operations to tree-ssa-reassoc pass 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 (two of two) adds to tree-ssa-reassociation code for repropagation of unpacked bitwise-binary operations - like (X == 0) & (Y == 0), etc. Also it denormalizes bitwise-not operations on bitwise-binary tree chains - eg ~X & ~Y -> ~(X | Y). ChangeLog 2011-10-04 Kai Tietz * tree-ssa-reassoc.c (walk_bitwise_stmt_elems): Helper routine to build vectored representation of bitwise-binary tree chain. (rebuild_vector_tree): Build out of a vectored tree-chain representation a tree-chain. (operate_bitwise_xor_stmt): Handle bitwise-xor denormalization. (merge_bitwise_compares): Special helper for rebuilding denormalized form of comparison to zero list. (operate_bitwise_stmt): Handle bitwise-binary denormalization. (repropagate_bitwise): New static function. (execute_reassoc): Use repropagate_bitwise. ChangeLog 2011-10-04 Kai Tietz * gcc.dg/tree-ssa/reassoc-32.c: New file. * gcc.dg/tree-ssa/reassoc-33.c: New file. * gcc.dg/tree-ssa/reassoc-34.c: New file. * gcc.dg/tree-ssa/reassoc-35.c: New file. 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 @@ -2658,6 +3113,648 @@ linearize_expr_tree (VEC(operand_entry_t add_to_ops_vec (ops, binrhs); } +/* Split up a binary tree-chain of code CODE - starting at STMT - into four + different kinds: + - vector VCST stores constant values. + - vector VNOT stores bitwise-not expressions. + - vector VCMP_ZERO stores comparisons to zero. + - vector VEXRR stores the remaining rest. */ + +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) **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, vexpr); + else if (gimple_assign_rhs_code (s) == BIT_NOT_EXPR) + 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); + else + 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, vexpr); + else if (gimple_assign_rhs_code (s) == BIT_NOT_EXPR) + 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); + else + 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 the 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 has value TRUE, then the RHS1 operand of VEC elements + are used for combining. Otherwise the VEC elements itself are 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. This sequence + is made out of VNOT, VEXPR, and TCST. + It returns TRUE, if tree-chain PGSI - starting at STMT - was modified, + otherwise FALSE. */ + +static bool +operate_bitwise_xor_stmt (gimple_stmt_iterator *pgsi, gimple stmt, tree tcst, + VEC(tree, heap) *vnot, + VEC(tree, heap) *vexpr) +{ + 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); + gimple_assign_set_rhs_with_ops (pgsi, BIT_NOT_EXPR, l, NULL_TREE); + } + else + { + if (r) + gimple_assign_set_rhs_with_ops (pgsi, BIT_XOR_EXPR, l, r); + else + gimple_assign_set_rhs_from_tree (pgsi, l); + } + return true; +} + +/* This function merges:compares + It merges VCMP elements + - (X != 0) | (Y != 0) -> (X | Y) != 0 + - (X == 0) & (Y == 0) -> (X | Y) == 0. + Additionally it sorts and merges for the new generated left-hand + bitwise-or tree-chain the bitwise-not expressions. + + CODE specifies the final compare expression code. It can be either + EQ_EXPR, or NE_EXPR. + + If PGSI is not NULL, then final compare instruction + gets assigned to the statement it points to. Otherwise an new + temporary is created for the comparison 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. + For the bitwise-and case, we need to make sure sign-expansion is + done always for type-expansion. */ + +static void +merge_bitwise_compares (VEC(tree, heap) **vcmp, VEC(tree, heap) **vexpr, + enum tree_code code, gimple_stmt_iterator *pgsi) +{ + unsigned int i; + unsigned int len = VEC_length (tree, *vcmp); + tree l, r, x, cmp_type = NULL_TREE; + VEC(tree, heap) *vtmp = NULL; + VEC(tree, heap) *vtmp_not = NULL; + enum tree_code cmp_code; + + /* If we have just one compare-element, then simply + move it to VEXPR vector and return. */ + if (len <= 1) + { + if (VEC_iterate (tree, (*vcmp), 0, (x))) + VEC_safe_push (tree, heap, *vexpr, x); + + 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 (TREE_CODE (r) != SSA_NAME + || (s = SSA_NAME_DEF_STMT (r)) == NULL + || !is_gimple_assign (s) + || gimple_assign_rhs_code (s) != BIT_NOT_EXPR) + { + i++; + continue; + } + 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), + BIT_AND_EXPR, l, r, s); + VEC_ordered_remove (tree, *vcmp, i); + } + else + ++i; + } + if (l != NULL_TREE) + VEC_safe_push (tree, heap, vtmp_not, l); + l = NULL_TREE; + for (i = 0; VEC_iterate (tree, (*vcmp), (i), (x));) + { + gimple s2; + gimple s = SSA_NAME_DEF_STMT (x); + r = gimple_assign_rhs1 (s); + if (TREE_CODE (r) == SSA_NAME + && (s2 = SSA_NAME_DEF_STMT (r)) != NULL + && is_gimple_assign (s2) + && gimple_assign_rhs_code (s2) == BIT_NOT_EXPR) + { + i++; + continue; + } + 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), + BIT_IOR_EXPR, l, r, s); + VEC_ordered_remove (tree, *vcmp, i); + } + else + ++i; + } + if (l != NULL_TREE) + VEC_safe_push (tree, heap, vtmp, l); + } + VEC_free (tree, heap, *vcmp); + *vcmp = NULL; + + /* Combine elements in vector vtmp_not and put them to vtmp. */ + l = NULL_TREE; + r = NULL_TREE; + + FOR_EACH_VEC_ELT (tree, vtmp_not, i, x) + { + tree type; + type = TREE_TYPE (x); + + if (TYPE_UNSIGNED (type) && VEC_length (tree, vtmp_not) > 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, BIT_AND_EXPR, l, x, SSA_NAME_DEF_STMT (x)); + } + } + if (l != NULL_TREE) + { + l = make_new_tmp_statement (TREE_TYPE (l), BIT_NOT_EXPR, l, NULL_TREE, + SSA_NAME_DEF_STMT (l)); + VEC_safe_push (tree, heap, vtmp, l); + } + VEC_free (tree, heap, vtmp_not); + vtmp_not = 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 (!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, BIT_IOR_EXPR, l, x, SSA_NAME_DEF_STMT (x)); + } + } + + /* - (X == 0) & (Y == 0) -> (X | Y) == 0 + - (X != 0) | (Y != 0) -> (X | Y) != 0 + */ + cmp_code = (code == BIT_AND_EXPR ? EQ_EXPR : NE_EXPR); + + if (!pgsi) + { + l = make_new_tmp_statement (cmp_type, + cmp_code, l, + build_zero_cst (TREE_TYPE (l)), + SSA_NAME_DEF_STMT (l)); + VEC_safe_push (tree, heap, *vexpr, l); + } + else + gimple_assign_set_rhs_with_ops (pgsi, cmp_code, l, + build_zero_cst (TREE_TYPE (l))); + 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 bool +operate_bitwise_stmt (gimple_stmt_iterator *pgsi, gimple stmt, enum tree_code code) +{ + unsigned int i = 0; + tree x, tcst = NULL_TREE; + tree tnot = NULL_TREE, torg = NULL_TREE; + VEC(tree, heap) *vcst = NULL; + VEC(tree, heap) *vnot = NULL; + VEC(tree, heap) *vcmp_zero = NULL; + VEC(tree, heap) *vexpr = NULL; + enum tree_code icode; + bool do_repropagate = false; + + gcc_assert (gimple_assign_rhs_code (stmt) == code); + + walk_bitwise_stmt_elems (stmt, code, &vcst, &vnot, + &vcmp_zero, &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) + 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, 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, vexpr); + return false; + } + + /* 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) + { + merge_bitwise_compares (&vcmp_zero, &vexpr, code, pgsi); + return true; + } + + merge_bitwise_compares (&vcmp_zero, &vexpr, code, NULL); + + /* If we deal only with constants, assign + calculated constant. */ + if (tcst && !vnot && !vexpr) + { + gimple_assign_set_rhs_from_tree (pgsi, tcst); + return true; + } + + if (code == BIT_XOR_EXPR) + { + operate_bitwise_xor_stmt (pgsi, stmt, tcst, vnot, vexpr); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return true; + } + + /* 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) + { + gimple_assign_set_rhs_with_ops (pgsi, BIT_NOT_EXPR, tnot, NULL_TREE); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return true; + } + + tnot = make_new_tmp_statement (TREE_TYPE (tnot), BIT_NOT_EXPR, tnot, + NULL_TREE, SSA_NAME_DEF_STMT (tnot)); + if (torg) + { + if (!tcst) + { + gimple_assign_set_rhs_with_ops (pgsi, code, tnot, torg); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return true; + } + tnot = make_new_tmp_statement (TREE_TYPE (tnot), code, tnot, torg, + SSA_NAME_DEF_STMT (tnot)); + } + gimple_assign_set_rhs_with_ops (pgsi, code, tnot, tcst); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return true; + } + if (!tcst) + torg = rebuild_vector_tree (vexpr, code, &tcst, false); + else + torg = rebuild_vector_tree (vexpr, code, NULL, false); + if (tcst) + gimple_assign_set_rhs_with_ops (pgsi, code, torg, tcst); + else + gimple_assign_set_rhs_from_tree (pgsi, torg); + VEC_free (tree, heap, vnot); + VEC_free (tree, heap, vexpr); + return true; +} + +/* Repropagate bitwise-operations back to de-normalized form. + ~X op ~Y -> ~(X op' Y), (X != 0) | (Y != 0) -> (X | Y) != 0, + (X == 0) & (Y == 0) -> (X | Y) == 0, and + ~X ==/!= 0 -> X ==/!= ~0. */ + +static void +repropagate_bitwise (basic_block bb) +{ + gimple_stmt_iterator gsi; + basic_block son; + + /* First do combine and bitwise-not sinking. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple sub; + gimple stmt = gsi_stmt (gsi); + enum tree_code code; + tree l, r, lhs; + + if (!is_gimple_assign (stmt)) + continue; + + code = gimple_assign_rhs_code (stmt); + if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR + && code != BIT_XOR_EXPR) + continue; + + /* If user of this statement has same tree-code as this statement and + this STMT has single use, then skip the processing for this STMT for + performance reasons. */ + lhs = gimple_assign_lhs (stmt); + if (has_single_use (lhs) + && (sub = get_single_immediate_use (lhs)) != NULL + && is_gimple_assign (sub) + && gimple_assign_rhs_code (sub) == code) + continue; + l = gimple_assign_rhs1 (stmt); + r = gimple_assign_rhs2 (stmt); + if (!operate_bitwise_stmt (&gsi, stmt, code)) + continue; + stmt = gsi_stmt (gsi); + update_stmt (stmt); + remove_stmt_chain (l); + remove_stmt_chain (r); + } + + /* Now we are doing transformation ~X !=/== CST -> X !=/== ~CST. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple sub; + gimple stmt = gsi_stmt (gsi); + enum tree_code code; + tree l, r; + + if (!is_gimple_assign (stmt)) + continue; + + code = gimple_assign_rhs_code (stmt); + if (code != EQ_EXPR && code != NE_EXPR) + continue; + l = gimple_assign_rhs1 (stmt); + r = gimple_assign_rhs2 (stmt); + if (TREE_CODE (l) != SSA_NAME + || TREE_CODE (r) != INTEGER_CST + || (sub = SSA_NAME_DEF_STMT (l)) == NULL + || !is_gimple_assign (sub) + || gimple_assign_rhs_code (sub) != BIT_NOT_EXPR + || !INTEGRAL_TYPE_P (TREE_TYPE (l))) + continue; + gimple_assign_set_rhs_with_ops (&gsi, code, gimple_assign_rhs1 (sub), + fold_build1 (BIT_NOT_EXPR, + TREE_TYPE (l), r)); + update_stmt (stmt); + remove_stmt_chain (l); + remove_stmt_chain (r); + } + + for (son = first_dom_son (CDI_DOMINATORS, bb); + son; + son = next_dom_son (CDI_DOMINATORS, son)) + repropagate_bitwise (son); +} + /* Repropagate the negates back into subtracts, since no other pass currently does it. */ @@ -3072,6 +4194,7 @@ execute_reassoc (void) do_reassoc (); repropagate_negates (); + repropagate_bitwise (ENTRY_BLOCK_PTR); fini_reassoc (); return 0; 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,20 @@ +/* { 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" 1 "optimized"} } */ +/* { dg-final { scan-tree-dump-times " != -1" 1 "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,20 @@ +/* { 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" 1 "optimized"} } */ +/* { dg-final { scan-tree-dump-times " != -1" 1 "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,26 @@ +/* { 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" 1 "optimized"} } */ +/* { dg-final { scan-tree-dump-times " != -1" 1 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */