From: Kai Tietz <ktietz70@googlemail.com>
To: Richard Guenther <richard.guenther@gmail.com>
Cc: Kai Tietz <ktietz@redhat.com>, gcc-patches@gcc.gnu.org
Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
Date: Fri, 01 Jul 2011 15:23:00 -0000 [thread overview]
Message-ID: <BANLkTikW7iOuW8d=ggrzWmzgbZMupmBjXg@mail.gmail.com> (raw)
In-Reply-To: <BANLkTi=6spAr50qKsDsOYv+XdnfBSxebSw@mail.gmail.com>
So updated patch (bootstrapped and tested for all standard languages
plus Ada and Obj-C++) on x86_64-pc-linux-gnu host.
Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1602,6 +1602,156 @@ simplify_builtin_call (gimple_stmt_itera
return false;
}
+/* Checks if expression has type of one-bit precision, or is a known
+ truth-valued expression. */
+static bool
+truth_valued_ssa_name (tree name)
+{
+ gimple def;
+ tree type = TREE_TYPE (name);
+
+ if (!INTEGRAL_TYPE_P (type))
+ return false;
+ /* Don't check here for BOOLEAN_TYPE as the precision isn't
+ necessarily one and so ~X is not equal to !X. */
+ if (TYPE_PRECISION (type) == 1)
+ return true;
+ def = SSA_NAME_DEF_STMT (name);
+ if (is_gimple_assign (def))
+ return truth_value_p (gimple_assign_rhs_code (def));
+ return false;
+}
+
+/* Helper routine for simplify_bitwise_binary_1 function.
+ Return for the SSA name NAME the expression X if it mets condition
+ NAME = !X. Otherwise return NULL_TREE.
+ Detected patterns for NAME = !X are:
+ !X and X == 0 for X with integral type.
+ X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
+static tree
+lookup_logical_inverted_value (tree name)
+{
+ tree op1, op2;
+ enum tree_code code;
+ gimple def;
+
+ /* If name has none-intergal type, or isn't a SSA_NAME, then
+ return. */
+ if (TREE_CODE (name) != SSA_NAME
+ || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
+ return NULL_TREE;
+ def = SSA_NAME_DEF_STMT (name);
+ if (!is_gimple_assign (def))
+ return NULL_TREE;
+
+ code = gimple_assign_rhs_code (def);
+ op1 = gimple_assign_rhs1 (def);
+ op2 = NULL_TREE;
+
+ /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
+ If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR,
+ or BIT_NOT_EXPR, then return. */
+ if (code == EQ_EXPR || code == NE_EXPR
+ || code == BIT_XOR_EXPR)
+ op2 = gimple_assign_rhs2 (def);
+
+ switch (code)
+ {
+ case TRUTH_NOT_EXPR:
+ return op1;
+ case BIT_NOT_EXPR:
+ if (truth_valued_ssa_name (name))
+ return op1;
+ break;
+ case EQ_EXPR:
+ /* Check if we have X == 0 and X has an integral type. */
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
+ break;
+ if (integer_zerop (op2))
+ return op1;
+ break;
+ case NE_EXPR:
+ /* Check if we have X != 1 and X is a truth-valued. */
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
+ break;
+ if (integer_onep (op2) && truth_valued_ssa_name (op1))
+ return op1;
+ break;
+ case BIT_XOR_EXPR:
+ /* Check if we have X ^ 1 and X is truth valued. */
+ if (integer_onep (op2) && truth_valued_ssa_name (op1))
+ return op1;
+ break;
+ default:
+ break;
+ }
+
+ return NULL_TREE;
+}
+
+/* Try to optimize patterns X & !X -> zero, X | !X -> one, and
+ X ^ !X -> one, if type of X is valid for this.
+
+ See for list of detected logical-not patterns the
+ lookup_logical_inverted_value function. */
+static tree
+simplify_bitwise_binary_1 (enum tree_code code, tree arg1,
+ tree arg2)
+{
+ tree a1not, a2not;
+ tree op = NULL_TREE;
+
+ /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
+ if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
+ && code != BIT_XOR_EXPR)
+ return NULL_TREE;
+
+ /* First check if operands ARG1 and ARG2 are equal. */
+ if (operand_equal_p (arg1, arg2, 0))
+ return NULL_TREE;
+ /* See if we have in arguments logical-not patterns. */
+ a1not = lookup_logical_inverted_value (arg1);
+ a2not = lookup_logical_inverted_value (arg2);
+
+ /* If there are no logical-not in arguments, return NULL_TREE. */
+ if (!a1not && !a2not)
+ return NULL_TREE;
+
+ /* If both arguments are logical-not patterns, then try to fold
+ them or return NULL_TREE. */
+ if (a1not && a2not)
+ {
+ /* If logical-not operands of ARG1 and ARG2 are equal, then fold
+ them.. */
+ if (operand_equal_p (a1not, a2not, 0))
+ {
+ /* !X & !X -> !X, and !X | !X -> !X. */
+ if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ return arg1;
+ /* !X ^ !X -> 0. */
+ return integer_zero_node;
+ }
+ return NULL_TREE;
+ }
+
+ if (a2not && operand_equal_p (arg1, a2not, 0))
+ op = arg1;
+ else if (a1not && operand_equal_p (arg2, a1not, 0))
+ op = arg2;
+ else
+ return NULL_TREE;
+
+ /* X & !X -> 0. */
+ if (code == BIT_AND_EXPR)
+ return integer_zero_node;
+ /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
+ if (truth_valued_ssa_name (op))
+ return integer_one_node;
+
+ /* ??? Otherwise result is (X != 0 ? X : 1. not handled. */
+ return NULL_TREE;
+}
+
/* Simplify bitwise binary operations.
Return true if a transformation applied, otherwise return false. */
@@ -1768,7 +1918,31 @@ simplify_bitwise_binary (gimple_stmt_ite
update_stmt (stmt);
return true;
}
+ /* Try simple folding for X op !X, and X op X. */
+ res = simplify_bitwise_binary_1 (code, arg1, arg2);
+ if (res != NULL_TREE && TREE_CODE (res) == INTEGER_CST)
+ {
+ res = fold_convert_loc (gimple_location (stmt),
+ TREE_TYPE (arg1), res);
+ gimple_assign_set_rhs_from_tree (gsi, res);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+ }
+ else if (res)
+ {
+ if (!useless_type_conversion_p (TREE_TYPE (arg1), TREE_TYPE (res)))
+ {
+ res = force_gimple_operand_gsi (gsi, res, true, NULL_TREE, true,
+ GSI_SAME_STMT);
+ gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+ res, NULL_TREE, NULL_TREE);
+ }
+ else
+ gimple_assign_set_rhs_from_tree (gsi, res);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+ }
return false;
}
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (char a, unsigned short b)
+{
+ return (a & !a) | (b & !b);
+}
+
+/* As long as comparisons aren't boolified and casts from boolean-types
+ aren't preserved, the folding of X & !X to zero fails. */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail
*-*-* } } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a)
+{
+ return (!a & 1) != (a == 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (short a)
+{
+ return (!a & 1) != ((a == 0) & 1);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned char a, _Bool b)
+{
+ return (!a & a) | (b & !b);
+}
+
+/* As long as comparisons aren't boolified and casts from boolean-types
+ aren't preserved, the folding of X & !X to zero fails. */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail
*-*-* } } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (long a, unsigned long b)
+{
+ return (a & (a == 0)) | (b & !b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned long a, long b)
+{
+ return (a & !a) | (b & (b == 0));
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+ return (a | !a) | (!b | b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+ return (a | (a == 0)) | ((b ^ 1) | b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+ return (a ^ !a) | (!b ^ b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (_Bool a, _Bool b)
+{
+ return (a ^ (a == 0)) | ((b == 0) ^ b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
next prev parent reply other threads:[~2011-07-01 15:23 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <196308741.816832.1309273513615.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com>
2011-06-28 15:40 ` Kai Tietz
2011-06-29 11:28 ` Richard Guenther
2011-06-29 12:52 ` Kai Tietz
2011-06-29 13:41 ` Kai Tietz
2011-06-30 12:22 ` Richard Guenther
2011-07-01 11:44 ` Kai Tietz
2011-07-01 12:53 ` Richard Guenther
2011-07-01 13:43 ` Kai Tietz
2011-07-01 13:57 ` Kai Tietz
2011-07-01 15:23 ` Kai Tietz [this message]
2011-07-04 13:17 ` Richard Guenther
2011-07-04 18:55 ` Kai Tietz
2011-07-07 14:34 ` Richard Guenther
2011-07-02 8:59 ` Kai Tietz
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='BANLkTikW7iOuW8d=ggrzWmzgbZMupmBjXg@mail.gmail.com' \
--to=ktietz70@googlemail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=ktietz@redhat.com \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).