Hello,
this patch adds the ability to gimple-fold to operate for truth and/or
operations
on folded binary-and/or optimized truth trees - as done by fold-const. As fold
converts trivial operations like (A && B) to (A & B) != 0, in most cases further
folding of truth and/or trees wasn't done.
folding will be again detected.
ChangeLog gcc/
2011-04-27 Kai Tietz
* gimple-fold.c (is_bit_ior_and): New helper function.
(fold_equal_and_or): New helper function for truth &&
and || logic folding with treating binary optimization.
(maybe_fold_and_comparisons): Folding for and.
(maybe_fold_or_comparisons): Folding for or.
ChangeLog gcc/testsuite/
2011-04-27 Kai Tietz
* gcc.dg/binop-tand1.c: New.
* gcc.dg/binop-tand2.c: New.
* gcc.dg/binop-tor1.c: New.
* gcc.dg/binop-tor2.c: New.
Tested for x86_64-pc-linux-gnu and x86_64-w64-mingw32. Ok for apply?
Regards,
Kai
Index: gcc/gcc/gimple-fold.c
===================================================================
--- gcc.orig/gcc/gimple-fold.c 2011-04-26 13:25:59.000000000 +0200
+++ gcc/gcc/gimple-fold.c 2011-04-27 20:08:50.276783700 +0200
@@ -2300,6 +2300,85 @@ and_comparisons_1 (enum tree_code code1,
return NULL_TREE;
}
+/* Checks if the binary logic can be expand for truth logic specified by the
+ IS_AND flag. We assume that C is EQ_EXPR or NE_EXPR. If we see a binary
+ or the variable IS_IOR is set to true, otherwise it is set to zero. */
+
+static bool
+is_bit_ior_and (tree op, enum tree_code c, bool *is_ior, bool is_and)
+{
+ enum tree_code code;
+ gimple s;
+
+ gcc_assert (c == EQ_EXPR || c == NE_EXPR);
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign ((s = SSA_NAME_DEF_STMT (op))))
+ return false;
+ code = gimple_assign_rhs_code (s);
+ if (code != BIT_IOR_EXPR && code != BIT_AND_EXPR)
+ return false;
+ if (is_and)
+ {
+ if ((code == BIT_IOR_EXPR && c == NE_EXPR)
+ || (code != BIT_IOR_EXPR && c == EQ_EXPR))
+ return false;
+ }
+ else
+ {
+ if ((code == BIT_IOR_EXPR && c != NE_EXPR)
+ || (code != BIT_IOR_EXPR && c != EQ_EXPR))
+ return false;
+ }
+ *is_ior = (code == BIT_IOR_EXPR);
+ return true;
+}
+
+/* Try to unfold truth and/or logic by watching into binary and/or optimized
+ truth logic. */
+static tree
+fold_equal_and_or (tree l, bool l_true, int l_and, tree r, bool r_true, int
is_and)
+{
+ gimple s;
+ if (operand_equal_p (l, r, 0))
+ {
+ if (l_true == r_true)
+ return l;
+ return (is_and ? boolean_false_node : boolean_true_node);
+ }
+ if (TREE_CODE (l) == SSA_NAME && is_gimple_assign ((s = SSA_NAME_DEF_STMT
(l)))
+ && gimple_assign_rhs_code (s) == (l_and ? BIT_AND_EXPR : BIT_IOR_EXPR))
+ {
+ tree l1, l2, t1, t2;
+ gimple_stmt_iterator gsi;
+ l1 = gimple_assign_rhs1 (s);
+ l2 = gimple_assign_rhs1 (s);
+ t1 = fold_equal_and_or (l1, l_true, l_and, r, r_true, is_and);
+ if (t1 && ((is_and && integer_zerop (t1)) || (!is_and && integer_onep
(t1))))
+ return t1;
+ if (t1 && ((is_and && integer_zerop (t1)) || (!is_and && integer_zerop
(t1))))
+ return l2;
+
+ t2 = fold_equal_and_or (l2, l_true, l_and, r, r_true, is_and);
+ if (!t1 && !t2)
+ return NULL_TREE;
+ if (t2 && ((is_and && integer_zerop (t2)) || (!is_and && integer_onep
(t2))))
+ return t2;
+ if (t2 && ((is_and && integer_zerop (t2)) || (!is_and && integer_zerop
(t2))))
+ return l1;
+ if (t1)
+ t2 = l2;
+ else if (t2)
+ t1 = l1;
+ t1 = fold_build2 ((l_and ? BIT_AND_EXPR : BIT_IOR_EXPR), TREE_TYPE
(gimple_assign_lhs (s)),
+ t1, t2);
+ gsi = gsi_for_stmt (s);
+ gimple_assign_set_rhs_from_tree (&gsi, t1);
+ return gimple_assign_lhs (s);
+ }
+ return NULL;
+}
+
/* Try to simplify the AND of two comparisons, specified by
(OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
If this can be simplified to a single expression (without requiring
@@ -2311,11 +2390,43 @@ tree
maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
enum tree_code code2, tree op2a, tree op2b)
{
- tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+ tree t;
+ bool is_ior;
+
+ t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
if (t)
return t;
- else
- return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+ t = and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+ if (t)
+ return t;
+
+ if ((code1 != NE_EXPR && code1 != EQ_EXPR)
+ || (code2 != NE_EXPR && code2 != EQ_EXPR)
+ || !integer_zerop (op1b) || !integer_zerop (op2b))
+ return NULL_TREE;
+
+ if (is_bit_ior_and (op1a, code1, &is_ior, true))
+ {
+ t = fold_equal_and_or (op1a, (code1 == NE_EXPR), !is_ior, op2a, (code2
== NE_EXPR), 1);
+ if (t)
+ {
+ if (integer_zerop (t) || integer_onep (t))
+ return t;
+ return fold_build2 (code1, boolean_type_node, t, op1b);
+ }
+ }
+ if (is_bit_ior_and (op2a, code2, &is_ior, true))
+ {
+ t = fold_equal_and_or (op2a, (code2 == NE_EXPR), !is_ior, op1a, (code1
== NE_EXPR), 1);
+ if (t)
+ {
+ if (integer_zerop (t) || integer_onep (t))
+ return t;
+ return fold_build2 (code2, boolean_type_node, t, op2b);
+ }
+ }
+
+ return NULL;
}
/* Helper function for or_comparisons_1: try to simplify the OR of the
@@ -2761,11 +2872,43 @@ tree
maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
enum tree_code code2, tree op2a, tree op2b)
{
- tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
+ tree t;
+ bool is_ior;
+
+ t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
if (t)
return t;
- else
- return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+ t = or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
+ if (t)
+ return t;
+
+ if ((code1 != NE_EXPR && code1 != EQ_EXPR)
+ || (code2 != NE_EXPR && code2 != EQ_EXPR)
+ || !integer_zerop (op1b) || !integer_zerop (op2b))
+ return NULL_TREE;
+
+ if (is_bit_ior_and (op1a, code1, &is_ior, false))
+ {
+ t = fold_equal_and_or (op1a, (code1 == NE_EXPR), !is_ior, op2a, (code2
== NE_EXPR), 0);
+ if (t)
+ {
+ if (integer_zerop (t) || integer_onep (t))
+ return t;
+ return fold_build2 (code1, boolean_type_node, t, op1b);
+ }
+ }
+ if (is_bit_ior_and (op2a, code2, &is_ior, false))
+ {
+ t = fold_equal_and_or (op2a, (code2 == NE_EXPR), !is_ior, op1a, (code1
== NE_EXPR), 0);
+ if (t)
+ {
+ if (integer_zerop (t) || integer_onep (t))
+ return t;
+ return fold_build2 (code2, boolean_type_node, t, op2b);
+ }
+ }
+
+ return NULL;
}
@@ -2806,7 +2949,7 @@ gimple_fold_stmt_to_constant_1 (gimple s
else if (TREE_CODE (rhs) == ADDR_EXPR
&& !is_gimple_min_invariant (rhs))
{
- HOST_WIDE_INT offset;
+ HOST_WIDE_INT offset = 0;
tree base;
base = get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs, 0),
&offset,
Index: gcc/gcc/testsuite/gcc.dg/binop-tand1.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tand1.c 2011-04-27 21:31:19.276726900
+0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+ return ((!a && !b) && c && b && c && a);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+ it in the real test. */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-tand2.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tand2.c 2011-04-27 21:30:24.705797300
+0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+ return ((a && b) && (a & b) != 0 && c);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+ it in the real test. */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 5 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "&" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-tor1.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tor1.c 2011-04-27 21:37:35.889550600
+0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+ return ((a || b) || c || !b || c || !a);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+ it in the real test. */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-tor2.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-tor2.c 2011-04-27 21:41:04.270511700
+0200
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a, int b, int c)
+{
+ return ((a || b) || c || (a & b) == 0 || c);
+}
+
+/* We expect to see "<bb N>"; confirm that, so that we know to count
+ it in the real test. */
+/* { dg-final { scan-tree-dump-times "<bb\[^>\]*>" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
