* Re: [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern
@ 2015-01-21 21:24 Marc Glisse
2015-01-22 9:24 ` Richard Biener
0 siblings, 1 reply; 5+ messages in thread
From: Marc Glisse @ 2015-01-21 21:24 UTC (permalink / raw)
To: gcc-patches; +Cc: rv
Hello,
(sorry for the broken thread, for some reason I haven't received any email
from gcc since about 10am, I'll investigate later)
+/* x & ~(x & y) -> x & ~y */
+(simplify
+ (bit_and:c @0 (bit_not (bit_and:c@2 @0 @1)))
+ (if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
+ (bit_and @0 (bit_not @1))))
Wouldn't it make more sense to put @2 on bit_not? If bit_and is used
multiple times, the transformation is neutral so it should be done as a
canonicalization. On the other hand, if bit_not is used multiple times,
the transformation adds an extra bit_not (which might be free when there
is an andn insn). So I believe the 2 main options are:
- move @2 on the bit_not
- don't test has_single_use at all
--
Marc Glisse
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern
2015-01-21 21:24 [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern Marc Glisse
@ 2015-01-22 9:24 ` Richard Biener
2015-01-22 14:24 ` Rasmus Villemoes
0 siblings, 1 reply; 5+ messages in thread
From: Richard Biener @ 2015-01-22 9:24 UTC (permalink / raw)
To: Marc Glisse; +Cc: GCC Patches, rv
On Wed, Jan 21, 2015 at 9:00 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> (sorry for the broken thread, for some reason I haven't received any email
> from gcc since about 10am, I'll investigate later)
>
> +/* x & ~(x & y) -> x & ~y */
> +(simplify
> + (bit_and:c @0 (bit_not (bit_and:c@2 @0 @1)))
> + (if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
> + (bit_and @0 (bit_not @1))))
>
> Wouldn't it make more sense to put @2 on bit_not? If bit_and is used
> multiple times, the transformation is neutral so it should be done as a
> canonicalization. On the other hand, if bit_not is used multiple times, the
> transformation adds an extra bit_not (which might be free when there is an
> andn insn). So I believe the 2 main options are:
> - move @2 on the bit_not
> - don't test has_single_use at all
I tend to favor not testing has_single_use at all.
Richard.
> --
> Marc Glisse
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern
2015-01-22 9:24 ` Richard Biener
@ 2015-01-22 14:24 ` Rasmus Villemoes
0 siblings, 0 replies; 5+ messages in thread
From: Rasmus Villemoes @ 2015-01-22 14:24 UTC (permalink / raw)
To: Richard Biener; +Cc: Marc Glisse, GCC Patches
On Thu, Jan 22 2015, Richard Biener <richard.guenther@gmail.com> wrote:
> On Wed, Jan 21, 2015 at 9:00 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> (sorry for the broken thread, for some reason I haven't received any email
>> from gcc since about 10am, I'll investigate later)
>>
>> +/* x & ~(x & y) -> x & ~y */
>> +(simplify
>> + (bit_and:c @0 (bit_not (bit_and:c@2 @0 @1)))
>> + (if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
>> + (bit_and @0 (bit_not @1))))
>>
>> Wouldn't it make more sense to put @2 on bit_not? If bit_and is used
>> multiple times, the transformation is neutral so it should be done as a
>> canonicalization. On the other hand, if bit_not is used multiple times, the
>> transformation adds an extra bit_not (which might be free when there is an
>> andn insn). So I believe the 2 main options are:
>> - move @2 on the bit_not
>> - don't test has_single_use at all
>
> I tend to favor not testing has_single_use at all.
Does this apply only to this pattern, to this pattern and its dual
(3/4), or to all four?
Rasmus
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: RFC: Two minor optimization patterns
@ 2015-01-14 14:01 Richard Biener
2015-01-21 10:50 ` [PATCH 0/4] A few " Rasmus Villemoes
0 siblings, 1 reply; 5+ messages in thread
From: Richard Biener @ 2015-01-14 14:01 UTC (permalink / raw)
To: Rasmus Villemoes; +Cc: Andrew Pinski, GCC Patches
On Wed, Jan 14, 2015 at 1:23 PM, Rasmus Villemoes <rv@rasmusvillemoes.dk> wrote:
> On Wed, Jan 14 2015, Richard Biener <richard.guenther@gmail.com> wrote:
>
>> On Tue, Jan 13, 2015 at 11:47 PM, Andrew Pinski <pinskia@gmail.com> wrote:
>>> On Tue, Jan 13, 2015 at 2:41 PM, Rasmus Villemoes <rv@rasmusvillemoes.dk> wrote:
>>>> [My first attempt at submitting a patch for gcc, so please forgive me
>>>> if I'm not following the right protocol.]
>>>
>>> There are a few things missing. For one, a testcase or two for the
>>> added optimizations.
>
> I'll see what I can come up with. Thanks for the pointers.
>
>>>> Sometimes rounding a variable to the next even integer is written x += x
>>>> & 1. This usually means using an extra register (and hence at least an
>>>> extra mov instruction) compared to the equivalent x = (x + 1) & ~1. The
>>>> first pattern below tries to do this transformation.
>>>>
>>>> While playing with various ways of rounding down, I noticed that gcc
>>>> already optimizes all of x-(x&3), x^(x&3) and x&~(x&3) to simply
>>>> x&~3.
>>
>> Does it also handle x+(x&3)?
>
> I'm not sure what 'it' refers to, and I'm also not sure how you think
> x+(x&3) could be rewritten.
I was just guessing.
>> Where does it handle x - (x&3)?
>
> If by 'it' you mean gcc, I tried looking for a pattern matching this,
> but couldn't find it, so I don't know where it is handled. I can just
> see by running gcc-5.0 -fdump-tree-original -O2 -c opt.c that "x - (x &
> 3)" is rewritten as x & -4 (which is of course the same as x & ~3).
That's done in fold-const.c:fold_binary_loc here:
/* Fold A - (A & B) into ~B & A. */
if (!TREE_SIDE_EFFECTS (arg0)
&& TREE_CODE (arg1) == BIT_AND_EXPR)
{
...
(note that patterns are not fully moved to match.pd yet)
> Btw,
> I now see that neither x&~(x&3) or x&~(x&y) are rewritten that early,
> but objdump -d shows that the end result is the same.
>
>> That is, doesn't the pattern also work for constants other than 1?
>
> Here I assume that 'the pattern' refers to the first pattern, and the
> answer is 'not immediately'. To round up a number to the next multiple
> of 2^k we need to add the negative of that number modulo 2^k. It just so
> happens that for k=1 we have x==-x for both possible values of x. So
> with a little tweak, this does in fact lead to an optimization
> opportunity, namely x + ((-x) & m) -> (x + m) & ~m whenever m is one
> less than a power of 2. I don't know how to check for m satisfying this
> in the match.pd language.
you'd need to write some C code involving trees in a if/with. We do
have a integer_pow2p predicate but not a integer_one_less_than_pow2p
one.
>
>> Please put it before the abs simplifications after the last one handing
>> bit_and/bit_ior.
>
> OK, will do.
Thanks,
Richard.
> Rasmus
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH 0/4] A few optimization patterns
2015-01-14 14:01 RFC: Two minor optimization patterns Richard Biener
@ 2015-01-21 10:50 ` Rasmus Villemoes
2015-01-21 10:55 ` [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern Rasmus Villemoes
0 siblings, 1 reply; 5+ messages in thread
From: Rasmus Villemoes @ 2015-01-21 10:50 UTC (permalink / raw)
To: GCC Patches; +Cc: Richard Biener, Andrew Pinski, Rasmus Villemoes
This adds four optimization patterns to match.pd, along with trivial
test cases. Compiles and works as expected, and 'make check' on x86_64
gives the same number of "unexpected failures" before and after (8
from gfortran.dg/guality/pr41558.f90, 1 from failing to compile
gcc.dg/plugin/ggcplug.c).
I know almost nothing about the internals of gcc, so 4/4 may very well
be considered ugly - it was what I could stitch together from pieces I
picked up here and there.
Rasmus Villemoes (4):
match.pd: Add x + (x & 1) -> (x + 1) & ~1 pattern
match.pd: Add x & ~(x & y) -> x & ~y pattern
match.pd: Add x | ~(x | y) -> x | ~y pattern
match.pd: Add x + ((-x) & m) -> (x + m) & ~m pattern
gcc/match.pd | 27 ++++++++++++++++++
gcc/testsuite/gcc.dg/20150120-1.c | 51 +++++++++++++++++++++++++++++++++
gcc/testsuite/gcc.dg/20150120-2.c | 32 +++++++++++++++++++++
gcc/testsuite/gcc.dg/20150120-3.c | 32 +++++++++++++++++++++
gcc/testsuite/gcc.dg/20150120-4.c | 59 +++++++++++++++++++++++++++++++++++++++
5 files changed, 201 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/20150120-1.c
create mode 100644 gcc/testsuite/gcc.dg/20150120-2.c
create mode 100644 gcc/testsuite/gcc.dg/20150120-3.c
create mode 100644 gcc/testsuite/gcc.dg/20150120-4.c
--
2.1.3
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern
2015-01-21 10:50 ` [PATCH 0/4] A few " Rasmus Villemoes
@ 2015-01-21 10:55 ` Rasmus Villemoes
2015-05-01 18:29 ` Jeff Law
0 siblings, 1 reply; 5+ messages in thread
From: Rasmus Villemoes @ 2015-01-21 10:55 UTC (permalink / raw)
To: GCC Patches; +Cc: Richard Biener, Andrew Pinski, Rasmus Villemoes
gcc.dg/20150120-2.c: New test
Clearing a certain subset of bits, for example to round down x to a
multiple of a power of 2, is sometimes written x & ~(x & y), where y
may or may not be a constant. It is shorter to use x & ~y,
particularly when y is a constant. gcc already does this when it is
spelled x - (x & y) or x ^ (x & y).
Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
---
gcc/match.pd | 6 ++++++
gcc/testsuite/gcc.dg/20150120-2.c | 32 ++++++++++++++++++++++++++++++++
2 files changed, 38 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/20150120-2.c
diff --git gcc/match.pd gcc/match.pd
index ecefcfb..d25fc3a 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -261,6 +261,12 @@ along with GCC; see the file COPYING3. If not see
(if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
(bit_and (plus @0 @1) (bit_not @1))))
+/* x & ~(x & y) -> x & ~y */
+(simplify
+ (bit_and:c @0 (bit_not (bit_and:c@2 @0 @1)))
+ (if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
+ (bit_and @0 (bit_not @1))))
+
(simplify
(abs (negate @0))
(abs @0))
diff --git gcc/testsuite/gcc.dg/20150120-2.c gcc/testsuite/gcc.dg/20150120-2.c
new file mode 100644
index 0000000..976b654
--- /dev/null
+++ gcc/testsuite/gcc.dg/20150120-2.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+/* x & ~(x & y) -> x & ~y */
+int fn1 (int x, int y)
+{
+ return x & ~(x & y);
+}
+int fn2 (int x, int y)
+{
+ return ~(x & y) & x;
+}
+int fn3 (int x, int y)
+{
+ return x & ~(y & x);
+}
+int fn4 (int x, int y)
+{
+ return ~(y & x) & x;
+}
+int fn5 (int z)
+{
+ return z & ~(z & 3);
+}
+int fn6 (int z)
+{
+ return ~(z & 3) & z;
+}
+
+
+/* { dg-final { scan-tree-dump-times "~y & x" 4 "original" } } */
+/* { dg-final { scan-tree-dump-times "z & -4" 2 "original" } } */
--
2.1.3
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern
2015-01-21 10:55 ` [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern Rasmus Villemoes
@ 2015-05-01 18:29 ` Jeff Law
0 siblings, 0 replies; 5+ messages in thread
From: Jeff Law @ 2015-05-01 18:29 UTC (permalink / raw)
To: Rasmus Villemoes, GCC Patches; +Cc: Richard Biener, Andrew Pinski
[-- Attachment #1: Type: text/plain, Size: 972 bytes --]
On 01/21/2015 03:49 AM, Rasmus Villemoes wrote:
> gcc.dg/20150120-2.c: New test
>
> Clearing a certain subset of bits, for example to round down x to a
> multiple of a power of 2, is sometimes written x & ~(x & y), where y
> may or may not be a constant. It is shorter to use x & ~y,
> particularly when y is a constant. gcc already does this when it is
> spelled x - (x & y) or x ^ (x & y).
>
> Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
> ---
> gcc/match.pd | 6 ++++++
> gcc/testsuite/gcc.dg/20150120-2.c | 32 ++++++++++++++++++++++++++++++++
> 2 files changed, 38 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/20150120-2.c
I combined this pattern with its bit-ior 'dual' into a single pattern.
Then bootstrapped, regression tested, wrote the ChangeLog and installed
the result onto the trunk.
I'm attaching the final patch which includes the changes in #1, #2 and
#3 of this series for archival purposes.
jeff
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 4487 bytes --]
commit 0a66cfe379a8217c69705535303626d12aca0c5f
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date: Fri May 1 18:25:12 2015 +0000
* match.pd: New simplification patterns.
(x + (x & 1)) -> ((x + 1) & ~1)
(x & ~(x & y)) -> ((x & ~y))
(x | ~(x | y)) -> ((x | ~y))
* gcc.dg/20150120-1.c: New test.
* gcc.dg/20150120-2.c: New test.
* gcc.dg/20150120-3.c: New test.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@222697 138bc75d-0d04-0410-961f-82ee72b054a4
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 65816c7..e006b26 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2015-05-01 Rasmus Villemoes <rv@rasmusvillemoes.dk>
+
+ * match.pd: New simplification patterns.
+ (x + (x & 1)) -> ((x + 1) & ~1)
+ (x & ~(x & y)) -> ((x & ~y))
+ (x | ~(x | y)) -> ((x | ~y))
+
2015-05-01 Kyrylo Tkachov <kyrylo.tkachov@arm.com>
* target.def (attribute_table): Mention that struct attribute_spec
diff --git a/gcc/match.pd b/gcc/match.pd
index fc374de..87ecaf1 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -255,6 +255,20 @@ along with GCC; see the file COPYING3. If not see
(bitop @0 @0)
(non_lvalue @0)))
+/* x + (x & 1) -> (x + 1) & ~1 */
+(simplify
+ (plus:c @0 (bit_and@2 @0 integer_onep@1))
+ (if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
+ (bit_and (plus @0 @1) (bit_not @1))))
+
+/* x & ~(x & y) -> x & ~y */
+/* x | ~(x | y) -> x | ~y */
+(for bitop (bit_and bit_ior)
+ (simplify
+ (bitop:c @0 (bit_not (bitop:c@2 @0 @1)))
+ (if (TREE_CODE (@2) != SSA_NAME || has_single_use (@2))
+ (bitop @0 (bit_not @1)))))
+
(simplify
(abs (negate @0))
(abs @0))
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index bfdde3b..2aedc46 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2015-05-01 Rasmus Villemoes <rv@rasmusvillemoes.dk>
+
+ * gcc.dg/20150120-1.c: New test.
+ * gcc.dg/20150120-2.c: New test.
+ * gcc.dg/20150120-3.c: New test.
+
2015-05-01 David Edelsohn <dje.gcc@gmail.com>
* gcc.dg/debug/pr65771.c: Add "dg-add-options tls".
diff --git a/gcc/testsuite/gcc.dg/20150120-1.c b/gcc/testsuite/gcc.dg/20150120-1.c
new file mode 100644
index 0000000..18906c4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/20150120-1.c
@@ -0,0 +1,51 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+/* x + (x & 1) -> (x + 1) & ~1 */
+int
+fn1 (int x)
+{
+ return x + (x & 1);
+}
+int
+fn2 (int x)
+{
+ return (x & 1) + x;
+}
+int
+fn3 (int x)
+{
+ return x + (1 & x);
+}
+int
+fn4 (int x)
+{
+ return (1 & x) + x;
+}
+unsigned int
+fn5 (unsigned int x)
+{
+ return x + (x & 1);
+}
+unsigned int
+fn6 (unsigned int x)
+{
+ return (x & 1) + x;
+}
+unsigned int
+fn7 (unsigned int x)
+{
+ return x + (x % 2);
+}
+unsigned int
+fn8 (unsigned int x)
+{
+ return (x % 2) + x;
+}
+unsigned int
+fn9 (unsigned int x)
+{
+ return (1LL & x) + x;
+}
+
+/* { dg-final { scan-tree-dump-times "x \\+ 1" 9 "original" } } */
diff --git a/gcc/testsuite/gcc.dg/20150120-2.c b/gcc/testsuite/gcc.dg/20150120-2.c
new file mode 100644
index 0000000..976b654
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/20150120-2.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+/* x & ~(x & y) -> x & ~y */
+int fn1 (int x, int y)
+{
+ return x & ~(x & y);
+}
+int fn2 (int x, int y)
+{
+ return ~(x & y) & x;
+}
+int fn3 (int x, int y)
+{
+ return x & ~(y & x);
+}
+int fn4 (int x, int y)
+{
+ return ~(y & x) & x;
+}
+int fn5 (int z)
+{
+ return z & ~(z & 3);
+}
+int fn6 (int z)
+{
+ return ~(z & 3) & z;
+}
+
+
+/* { dg-final { scan-tree-dump-times "~y & x" 4 "original" } } */
+/* { dg-final { scan-tree-dump-times "z & -4" 2 "original" } } */
diff --git a/gcc/testsuite/gcc.dg/20150120-3.c b/gcc/testsuite/gcc.dg/20150120-3.c
new file mode 100644
index 0000000..322556f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/20150120-3.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+/* x | ~(x | y) -> x | ~y */
+int fn1 (int x, int y)
+{
+ return x | ~(x | y);
+}
+int fn2 (int x, int y)
+{
+ return ~(x | y) | x;
+}
+int fn3 (int x, int y)
+{
+ return x | ~(y | x);
+}
+int fn4 (int x, int y)
+{
+ return ~(y | x) | x;
+}
+int fn5 (int z)
+{
+ return z | ~(z | 3);
+}
+int fn6 (int z)
+{
+ return ~(z | 3) | z;
+}
+
+
+/* { dg-final { scan-tree-dump-times "~y \\| x" 4 "original" } } */
+/* { dg-final { scan-tree-dump-times "z \\| -4" 2 "original" } } */
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2015-05-01 18:29 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-01-21 21:24 [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern Marc Glisse
2015-01-22 9:24 ` Richard Biener
2015-01-22 14:24 ` Rasmus Villemoes
-- strict thread matches above, loose matches on Subject: below --
2015-01-14 14:01 RFC: Two minor optimization patterns Richard Biener
2015-01-21 10:50 ` [PATCH 0/4] A few " Rasmus Villemoes
2015-01-21 10:55 ` [PATCH 2/4] match.pd: Add x & ~(x & y) -> x & ~y pattern Rasmus Villemoes
2015-05-01 18:29 ` Jeff Law
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).