* [patch gimplifier]: Do folding on truth and/or trees
@ 2011-04-27 20:32 Kai Tietz
2011-04-27 20:33 ` Jakub Jelinek
2011-04-27 20:55 ` Richard Guenther
0 siblings, 2 replies; 5+ messages in thread
From: Kai Tietz @ 2011-04-27 20:32 UTC (permalink / raw)
To: GCC Patches; +Cc: Richard Henderson
[-- Attachment #1: Type: text/plain, Size: 880 bytes --]
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
[-- Attachment #2: gm_andor.txt --]
[-- Type: text/plain, Size: 9036 bytes --]
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" } } */
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch gimplifier]: Do folding on truth and/or trees
2011-04-27 20:32 [patch gimplifier]: Do folding on truth and/or trees Kai Tietz
@ 2011-04-27 20:33 ` Jakub Jelinek
2011-04-30 9:21 ` Hans-Peter Nilsson
2011-04-27 20:55 ` Richard Guenther
1 sibling, 1 reply; 5+ messages in thread
From: Jakub Jelinek @ 2011-04-27 20:33 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches, Richard Henderson
On Wed, Apr 27, 2011 at 10:03:34PM +0200, Kai Tietz wrote:
> --- /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);
For testing of gimple-fold folding (rather than fold-const), it would be
nice if you could also test those expressions from multiple
source statements with some temporaries. Otherwise, fold-const
will see everything together already when invoked from the FEs.
> +/* 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" } } */
Why do you test number of bb's? I don't see how is that relevant to
whether it has been optimized or not.
On the other side, it would be nice if you could test your testcases with
a cross compiler on a couple of other targets (e.g. powerpc64-linux
-m32,-m64, and/or arm, s390 or something similar). BRANCH_COST etc.
affect a lot how is this gimplified, and I believe there was a PR about
some of your recent testcases failing on powerpc.
You don't need to build cross binutils, all that is needed is
configure the cross and build just cc1, don't mind that the build
fails afterwards and just run it on your testcases by hand to see
what is in the dumps.
Jakub
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch gimplifier]: Do folding on truth and/or trees
2011-04-27 20:32 [patch gimplifier]: Do folding on truth and/or trees Kai Tietz
2011-04-27 20:33 ` Jakub Jelinek
@ 2011-04-27 20:55 ` Richard Guenther
2011-04-27 21:10 ` Richard Guenther
1 sibling, 1 reply; 5+ messages in thread
From: Richard Guenther @ 2011-04-27 20:55 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches, Richard Henderson
On Wed, Apr 27, 2011 at 10:03 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 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?
No. This is certainly the wrong place to do tree combining.
Richard.
> Regards,
> Kai
>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch gimplifier]: Do folding on truth and/or trees
2011-04-27 20:55 ` Richard Guenther
@ 2011-04-27 21:10 ` Richard Guenther
0 siblings, 0 replies; 5+ messages in thread
From: Richard Guenther @ 2011-04-27 21:10 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches, Richard Henderson
On Wed, Apr 27, 2011 at 10:26 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Wed, Apr 27, 2011 at 10:03 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 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?
>
> No. This is certainly the wrong place to do tree combining.
Either look into extending tree-ssa-forwprop.c or work on
http://gcc.gnu.org/ml/gcc-patches/2011-03/msg01099.html, thus fold
to piecewise gimple expressions so that the machinery can also
be used from value-numbering.
Richard.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [patch gimplifier]: Do folding on truth and/or trees
2011-04-27 20:33 ` Jakub Jelinek
@ 2011-04-30 9:21 ` Hans-Peter Nilsson
0 siblings, 0 replies; 5+ messages in thread
From: Hans-Peter Nilsson @ 2011-04-30 9:21 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: GCC Patches
On Wed, 27 Apr 2011, Jakub Jelinek wrote:
> You don't need to build cross binutils, all that is needed is
> configure the cross and build just cc1, don't mind that the build
> fails afterwards and just run it on your testcases by hand to see
> what is in the dumps.
FWIW "make all-gcc" doesn't fail these days (with libgcc at
toplevel); xgcc and cc1 are built the way you want them, yay.
(With reservations for autoconf:ed thingies that can't be tested
without an assembler/linker and thus are defaulted.)
brgds, H-P
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2011-04-30 2:42 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-04-27 20:32 [patch gimplifier]: Do folding on truth and/or trees Kai Tietz
2011-04-27 20:33 ` Jakub Jelinek
2011-04-30 9:21 ` Hans-Peter Nilsson
2011-04-27 20:55 ` Richard Guenther
2011-04-27 21:10 ` Richard Guenther
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).