From: Kai Tietz <ktietz@redhat.com>
To: gcc-patches@gcc.gnu.org
Cc: Richard Guenther <richard.guenther@gmail.com>
Subject: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
Date: Tue, 28 Jun 2011 15:40:00 -0000 [thread overview]
Message-ID: <1457285936.816835.1309273517371.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com> (raw)
In-Reply-To: <196308741.816832.1309273513615.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com>
[-- Attachment #1: Type: text/plain, Size: 1298 bytes --]
Hello,
this patch implements the X op !X patterns within tree-ssa-forwprop.c without using here const-fold routines. Additionally it does some trivial folding for X op X. Implementation
also looks through [(type)] X op [(type)] !X, if type of X is integral and precision is suitable
for operation.
ChangeLog gcc/
2011-06-28 Kai Tietz <ktietz@redhat.com>
* tree-ssa-forwprop.c (operand_precision_onep): New
function.
(find_possible_not_expr_argument): Likewise.
(simplify_bitwise_binary_1): Likewise.
(simplify_bitwise_binary): Use simplify_bitwise_binary_1
for detecting various X op !X optimizations.
ChangeLog gcc/testsuite
2011-06-28 Kai Tietz <ktietz@redhat.com>
* gcc.dg/binop-notand1a.c: New test.
* gcc.dg/binop-notand2a.c: New test.
* gcc.dg/binop-notand3a.c: New test.
* gcc.dg/binop-notand4a.c: New test.
* gcc.dg/binop-notand5a.c: New test.
* gcc.dg/binop-notand6a.c: New test.
* gcc.dg/binop-notor1.c: New test.
* gcc.dg/binop-notor2.c: New test.
* gcc.dg/binop-notxor1.c: New test.
* gcc.dg/binop-notxor2.c: New test.
Bootstrapped and regression tested for all languages plus Ada and Obj-C for x86_64-pc-linux-gnu. Ok for apply?
Regards,
Kai
[-- Attachment #2: fold_fw.txt --]
[-- Type: text/plain, Size: 11510 bytes --]
Index: gcc-head/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-head.orig/gcc/tree-ssa-forwprop.c
+++ gcc-head/gcc/tree-ssa-forwprop.c
@@ -1674,6 +1674,189 @@ simplify_builtin_call (gimple_stmt_itera
return false;
}
+/* Checks if expression has type of one-bit precision, or is result of
+ a known boolean expression. */
+static bool
+operand_precision_onep (tree expr)
+{
+ enum tree_code code;
+
+ do
+ {
+ code = TREE_CODE (expr);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (expr)))
+ return false;
+ if (TYPE_PRECISION (TREE_TYPE (expr)) == 1)
+ return true;
+ if (code == SSA_NAME)
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (expr);
+ if (!def_stmt || !is_gimple_assign (def_stmt))
+ break;
+ code = gimple_assign_rhs_code (def_stmt);
+ if (!CONVERT_EXPR_CODE_P (code))
+ break;
+ expr = gimple_assign_rhs1 (def_stmt);
+ }
+ else
+ break;
+ }
+ while (CONVERT_EXPR_CODE_P (code));
+ if (code == TRUTH_NOT_EXPR || TREE_CODE_CLASS (code) == tcc_comparison)
+ return true;
+ return false;
+}
+
+/* Helper routine for simplify_bitwise_binary_1 for counting
+ ignored type casts in CNT_CASTS, and finding possible match
+ returned in NEXPR. This function returns the first expression
+ not being a cast. */
+static tree
+find_possible_not_expr_argument (tree name, int *cnt_casts, tree *nexpr)
+{
+ enum tree_code code = ERROR_MARK;
+ *cnt_casts = 0;
+ *nexpr = NULL_TREE;
+
+ while (1)
+ {
+ tree op1, op2;
+ gimple def_stmt;
+ code = TREE_CODE (name);
+ /* If name has none-intergal type, or isn't a SSA_NAME, then
+ stop search. */
+ if (code != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
+ break;
+ def_stmt = SSA_NAME_DEF_STMT (name);
+ if (!def_stmt || !is_gimple_assign (def_stmt))
+ break;
+ code = gimple_assign_rhs_code (def_stmt);
+ op1 = gimple_assign_rhs1 (def_stmt);
+ op2 = NULL_TREE;
+ if (code == EQ_EXPR || code == BIT_XOR_EXPR)
+ op2 = gimple_assign_rhs2 (def_stmt);
+ else if (!CONVERT_EXPR_CODE_P (code)
+ && code != TRUTH_NOT_EXPR)
+ break;
+ if (code == TRUTH_NOT_EXPR
+ || (code == BIT_NOT_EXPR
+ && INTEGRAL_TYPE_P (name)
+ && operand_precision_onep (name)))
+ {
+ *nexpr = op1;
+ break;
+ }
+ else if (code == EQ_EXPR || code == BIT_XOR_EXPR)
+ {
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
+ break;
+ if (code == EQ_EXPR
+ && TREE_CODE (op2) == INTEGER_CST
+ && integer_zerop (op2))
+ *nexpr = op1;
+ else if (code == EQ_EXPR
+ && TREE_CODE (op1) == INTEGER_CST
+ && integer_zerop (op1))
+ *nexpr = op2;
+ else if (code == BIT_XOR_EXPR
+ && operand_precision_onep (op1)
+ && TREE_CODE (op2) == INTEGER_CST
+ && integer_onep (op2))
+ *nexpr = op1;
+ else if (code == BIT_XOR_EXPR
+ && operand_precision_onep (op2)
+ && TREE_CODE (op1) == INTEGER_CST
+ && integer_onep (op1))
+ *nexpr = op2;
+ break;
+ }
+ else if (!CONVERT_EXPR_CODE_P (code))
+ break;
+ /* Just allow sinking over one cast and this only for
+ integeral types. Otherwise value truncation
+ or intermediate float conversions need to be
+ considered. */
+ if (cnt_casts[0] != 0)
+ break;
+ cnt_casts[0] += 1;
+ name = op1;
+ }
+ return name;
+}
+
+/* Try to optimize patterns X & !X -> zero, X | !X -> one, and X ^ !X -> one,
+ if type of X allows this. Additional handle the variants X & X -> X,
+ X | X -> X, and X ^ X -> zero.
+ For integral type-casts we also pattern match (type) X op !X,
+ (type) X op (type) !X, and X op (type) !X sub-variants. */
+static tree
+simplify_bitwise_binary_1 (enum tree_code code, tree arg1, tree arg2)
+{
+ int a1cnt = 0, a2cnt = 0;
+ tree a1strip, a1expr;
+ tree a2strip, a2expr;
+ tree op = NULL_TREE;
+
+ if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
+ && code != BIT_XOR_EXPR)
+ return NULL_TREE;
+
+ if (operand_equal_p (arg1, arg2, 0))
+ {
+ if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ return arg1;
+ return integer_zero_node;
+ }
+ a1strip = find_possible_not_expr_argument (arg1, &a1cnt, &a1expr);
+ a2strip = find_possible_not_expr_argument (arg2, &a2cnt, &a2expr);
+
+ if (a1cnt == a2cnt && operand_equal_p (a1strip, a2strip, 0))
+ {
+ if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ return arg1;
+ return integer_zero_node;
+ }
+
+ if (!a1expr && !a2expr)
+ return NULL_TREE;
+
+ if (a2expr)
+ {
+ if (operand_equal_p (arg1, a2expr, 0)
+ || operand_equal_p (a1strip, a2expr, 0))
+ op = arg1;
+ }
+ if (!op && a1expr)
+ {
+ if (operand_equal_p (arg2, a1expr, 0)
+ || operand_equal_p (a2strip, a1expr, 0))
+ op = arg2;
+ }
+ if (!op)
+ return NULL_TREE;
+
+ /* We have found a X op !X operation. */
+ if (code == BIT_AND_EXPR)
+ return integer_zero_node;
+ else if (code == BIT_IOR_EXPR)
+ {
+ /* If X has type precision of one, then result is 1. */
+ if ((op == arg1 && operand_precision_onep (a1strip))
+ || (op == arg2 && operand_precision_onep (a2strip)))
+ return integer_one_node;
+ /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
+ }
+ else
+ {
+ /* Result for XOR for X with type precision of one is 1. */
+ if ((op == arg1 && operand_precision_onep (a1strip))
+ || (op == arg2 && operand_precision_onep (a2strip)))
+ 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. */
@@ -1862,7 +2045,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,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (char a, unsigned short b)
+{
+ return (a & !a) | (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-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,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned char a, _Bool b)
+{
+ return (!a & a) | (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-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 parent reply other threads:[~2011-06-28 15:05 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 [this message]
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
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=1457285936.816835.1309273517371.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com \
--to=ktietz@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--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).