* [patch][4.7] Enhance XOR handling in simplify-rtx.c
@ 2011-03-11 14:14 Chung-Lin Tang
2011-03-12 8:49 ` Chung-Lin Tang
2011-03-16 18:21 ` Richard Henderson
0 siblings, 2 replies; 6+ messages in thread
From: Chung-Lin Tang @ 2011-03-11 14:14 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1139 bytes --]
Hi,
this patch adds a bit more sophistication to the handled xor RTX cases
in foo().
This may look a bit ad hoc, but I am seeing it useful for some cases
where we combine zero_extend with (not (shift ...)). The supplied ARM
testcase demonstrates when 3-insn combining comes up with:
(set (reg:SI 145)
(xor:SI (and:SI (not:SI (reg/v:SI 135 [ crc ]))
(const_int 32767 [0x7fff]))
(const_int 65535 [0xffff])))
when it is actually equivalent to:
(set (reg:SI 145)
(ior:SI (reg/v:SI 135 [ x ])
(const_int 32768 [0x8000])))
This happens on ARM architecture levels v6 and above, due to its
possession of real zero_extend instructions. On ARMv5 and earlier, the
use of two shifts for zero extending actually helped to work around
this, due to staged combining effects of optimizing the shifts away one
by one...
Cross-tested using QEMU for ARM-Linux, currently undergoing x86
bootstrapping and testing. If results are clear, is this okay for trunk
when stage1 opens again?
Thanks,
Chung-Lin
* simplify-rtx.c (simplify_binary_operation_1): Handle
(xor (and A B) C) case when B and C are both constants.
[-- Attachment #2: xor.diff --]
[-- Type: text/plain, Size: 2025 bytes --]
Index: simplify-rtx.c
===================================================================
--- simplify-rtx.c (revision 170870)
+++ simplify-rtx.c (working copy)
@@ -2480,6 +2480,43 @@
XEXP (op0, 1), mode),
op1);
+ /* Given (xor (and A B) C), using P^Q == ~PQ | ~QP (concat as AND),
+ we can transform (AB)^C into:
+ A(~CB) | ~AC | ~BC
+ Attempt a few simplifications when B and C are both constants. */
+ if (GET_CODE (op0) == AND
+ && CONST_INT_P (op1) && CONST_INT_P (XEXP (op0, 1)))
+ {
+ rtx a = XEXP (op0, 0);
+ rtx b = XEXP (op0, 1);
+ rtx c = op1;
+ HOST_WIDE_INT bval = INTVAL (b);
+ HOST_WIDE_INT cval = INTVAL (c);
+
+ rtx na_c
+ = simplify_binary_operation (AND, mode,
+ simplify_gen_unary (NOT, mode, a, mode),
+ c);
+ if ((~cval & bval) == 0)
+ {
+ /* Try to simplify ~AC | ~BC. */
+ if (na_c != NULL_RTX)
+ return simplify_gen_binary (IOR, mode, na_c,
+ GEN_INT (~bval & cval));
+ }
+ else
+ {
+ /* If ~AC is zero, simplify A(~CB) | ~BC. */
+ if (na_c == const0_rtx)
+ {
+ rtx a_nc_b = simplify_gen_binary (AND, mode, a,
+ GEN_INT (~cval & bval));
+ return simplify_gen_binary (IOR, mode, a_nc_b,
+ GEN_INT (~bval & cval));
+ }
+ }
+ }
+
/* (xor (comparison foo bar) (const_int 1)) can become the reversed
comparison if STORE_FLAG_VALUE is 1. */
if (STORE_FLAG_VALUE == 1
Index: testsuite/gcc.target/arm/xor-and.c
===================================================================
--- testsuite/gcc.target/arm/xor-and.c (revision 0)
+++ testsuite/gcc.target/arm/xor-and.c (revision 0)
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O -march=armv6" } */
+
+unsigned short foo (unsigned short x)
+{
+ x ^= 0x4002;
+ x >>= 1;
+ x |= 0x8000;
+ return x;
+}
+
+/* { dg-final { scan-assembler "orr" } } */
+/* { dg-final { scan-assembler-not "mvn" } } */
+/* { dg-final { scan-assembler-not "uxth" } } */
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch][4.7] Enhance XOR handling in simplify-rtx.c
2011-03-11 14:14 [patch][4.7] Enhance XOR handling in simplify-rtx.c Chung-Lin Tang
@ 2011-03-12 8:49 ` Chung-Lin Tang
2011-03-16 18:21 ` Richard Henderson
1 sibling, 0 replies; 6+ messages in thread
From: Chung-Lin Tang @ 2011-03-12 8:49 UTC (permalink / raw)
To: gcc-patches
On 2011/3/11 10:14 PM, Chung-Lin Tang wrote:
> Hi,
> this patch adds a bit more sophistication to the handled xor RTX cases
> in foo().
>
> This may look a bit ad hoc, but I am seeing it useful for some cases
> where we combine zero_extend with (not (shift ...)). The supplied ARM
> testcase demonstrates when 3-insn combining comes up with:
> (set (reg:SI 145)
> (xor:SI (and:SI (not:SI (reg/v:SI 135 [ crc ]))
> (const_int 32767 [0x7fff]))
> (const_int 65535 [0xffff])))
>
> when it is actually equivalent to:
> (set (reg:SI 145)
> (ior:SI (reg/v:SI 135 [ x ])
> (const_int 32768 [0x8000])))
>
> This happens on ARM architecture levels v6 and above, due to its
> possession of real zero_extend instructions. On ARMv5 and earlier, the
> use of two shifts for zero extending actually helped to work around
> this, due to staged combining effects of optimizing the shifts away one
> by one...
>
> Cross-tested using QEMU for ARM-Linux, currently undergoing x86
> bootstrapping and testing. If results are clear, is this okay for trunk
> when stage1 opens again?
>
> Thanks,
> Chung-Lin
>
> * simplify-rtx.c (simplify_binary_operation_1): Handle
> (xor (and A B) C) case when B and C are both constants.
Bootstrap and test on i686 and x86_64 both completed with no regressions.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch][4.7] Enhance XOR handling in simplify-rtx.c
2011-03-11 14:14 [patch][4.7] Enhance XOR handling in simplify-rtx.c Chung-Lin Tang
2011-03-12 8:49 ` Chung-Lin Tang
@ 2011-03-16 18:21 ` Richard Henderson
2011-03-17 1:55 ` Chung-Lin Tang
1 sibling, 1 reply; 6+ messages in thread
From: Richard Henderson @ 2011-03-16 18:21 UTC (permalink / raw)
To: Chung-Lin Tang; +Cc: gcc-patches
On 03/11/2011 06:14 AM, Chung-Lin Tang wrote:
> + /* Given (xor (and A B) C), using P^Q == ~PQ | ~QP (concat as AND),
> + we can transform (AB)^C into:
> + A(~CB) | ~AC | ~BC
> + Attempt a few simplifications when B and C are both constants. */
I don't quite follow the step that gets you to that final form.
P^Q == ~PQ | ~QP
AB ^ C
== ~(AB)C | (~C)AB
== (~A)(~B)C | (~C)AB
== ?
I.e. how does
~AC | ~BC == (~A)(~B)C
?
r~
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch][4.7] Enhance XOR handling in simplify-rtx.c
2011-03-16 18:21 ` Richard Henderson
@ 2011-03-17 1:55 ` Chung-Lin Tang
2011-03-17 15:18 ` Richard Henderson
0 siblings, 1 reply; 6+ messages in thread
From: Chung-Lin Tang @ 2011-03-17 1:55 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc-patches
On 2011/3/17 03:21 AM, Richard Henderson wrote:
> On 03/11/2011 06:14 AM, Chung-Lin Tang wrote:
>> + /* Given (xor (and A B) C), using P^Q == ~PQ | ~QP (concat as AND),
>> + we can transform (AB)^C into:
>> + A(~CB) | ~AC | ~BC
>> + Attempt a few simplifications when B and C are both constants. */
>
> I don't quite follow the step that gets you to that final form.
>
> P^Q == ~PQ | ~QP
>
> AB ^ C
> == ~(AB)C | (~C)AB
> == (~A)(~B)C | (~C)AB
> == ?
You have to use DeMorgan's Law to distribute the ~ operator:
~(AB)C | (~C)AB
== (~A | ~B)C | A(~CB) // DeMorgan's Law
== ~AC | ~BC | A(~CB) // Distribute C over the |
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch][4.7] Enhance XOR handling in simplify-rtx.c
2011-03-17 1:55 ` Chung-Lin Tang
@ 2011-03-17 15:18 ` Richard Henderson
2011-03-21 7:38 ` Chung-Lin Tang
0 siblings, 1 reply; 6+ messages in thread
From: Richard Henderson @ 2011-03-17 15:18 UTC (permalink / raw)
To: Chung-Lin Tang; +Cc: gcc-patches
On 03/16/2011 06:55 PM, Chung-Lin Tang wrote:
> You have to use DeMorgan's Law to distribute the ~ operator:
Duh. Not sure where my head was yesterday.
Let's enhance the comment for someone else having an off day. Perhaps
/* Given (xor (and A B) C), using P^Q == ~P&Q | ~Q&P and DeMorgan's
we can transform
A&B ^ C == ~(A&B)&C | ~C&(A&B)
== (~A|~B)&C | A&B&~C
== ~A&C | ~B&C | A&B&~C
Attempt a few simplifications when B and C are both constants. */
> + if (GET_CODE (op0) == AND
> + && CONST_INT_P (op1) && CONST_INT_P (XEXP (op0, 1)))
Should have a newline before the second && here.
Ok with those changes.
r~
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch][4.7] Enhance XOR handling in simplify-rtx.c
2011-03-17 15:18 ` Richard Henderson
@ 2011-03-21 7:38 ` Chung-Lin Tang
0 siblings, 0 replies; 6+ messages in thread
From: Chung-Lin Tang @ 2011-03-21 7:38 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 820 bytes --]
On 2011/3/18 12:18 AM, Richard Henderson wrote:
> On 03/16/2011 06:55 PM, Chung-Lin Tang wrote:
>> You have to use DeMorgan's Law to distribute the ~ operator:
>
> Duh. Not sure where my head was yesterday.
>
> Let's enhance the comment for someone else having an off day. Perhaps
>
> /* Given (xor (and A B) C), using P^Q == ~P&Q | ~Q&P and DeMorgan's
> we can transform
> A&B ^ C == ~(A&B)&C | ~C&(A&B)
> == (~A|~B)&C | A&B&~C
> == ~A&C | ~B&C | A&B&~C
> Attempt a few simplifications when B and C are both constants. */
>
>> + if (GET_CODE (op0) == AND
>> + && CONST_INT_P (op1) && CONST_INT_P (XEXP (op0, 1)))
>
> Should have a newline before the second && here.
>
> Ok with those changes.
Thanks, committed patch attached below. Hope the comments are now
descriptive enough.
C.L.
[-- Attachment #2: xor-2.diff --]
[-- Type: text/plain, Size: 1609 bytes --]
Index: simplify-rtx.c
===================================================================
--- simplify-rtx.c (revision 171207)
+++ simplify-rtx.c (revision 171208)
@@ -2480,6 +2480,46 @@
XEXP (op0, 1), mode),
op1);
+ /* Given (xor (and A B) C), using P^Q == (~P&Q) | (~Q&P),
+ we can transform like this:
+ (A&B)^C == ~(A&B)&C | ~C&(A&B)
+ == (~A|~B)&C | ~C&(A&B) * DeMorgan's Law
+ == ~A&C | ~B&C | A&(~C&B) * Distribute and re-order
+ Attempt a few simplifications when B and C are both constants. */
+ if (GET_CODE (op0) == AND
+ && CONST_INT_P (op1)
+ && CONST_INT_P (XEXP (op0, 1)))
+ {
+ rtx a = XEXP (op0, 0);
+ rtx b = XEXP (op0, 1);
+ rtx c = op1;
+ HOST_WIDE_INT bval = INTVAL (b);
+ HOST_WIDE_INT cval = INTVAL (c);
+
+ rtx na_c
+ = simplify_binary_operation (AND, mode,
+ simplify_gen_unary (NOT, mode, a, mode),
+ c);
+ if ((~cval & bval) == 0)
+ {
+ /* Try to simplify ~A&C | ~B&C. */
+ if (na_c != NULL_RTX)
+ return simplify_gen_binary (IOR, mode, na_c,
+ GEN_INT (~bval & cval));
+ }
+ else
+ {
+ /* If ~A&C is zero, simplify A&(~C&B) | ~B&C. */
+ if (na_c == const0_rtx)
+ {
+ rtx a_nc_b = simplify_gen_binary (AND, mode, a,
+ GEN_INT (~cval & bval));
+ return simplify_gen_binary (IOR, mode, a_nc_b,
+ GEN_INT (~bval & cval));
+ }
+ }
+ }
+
/* (xor (comparison foo bar) (const_int 1)) can become the reversed
comparison if STORE_FLAG_VALUE is 1. */
if (STORE_FLAG_VALUE == 1
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-03-21 7:38 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-03-11 14:14 [patch][4.7] Enhance XOR handling in simplify-rtx.c Chung-Lin Tang
2011-03-12 8:49 ` Chung-Lin Tang
2011-03-16 18:21 ` Richard Henderson
2011-03-17 1:55 ` Chung-Lin Tang
2011-03-17 15:18 ` Richard Henderson
2011-03-21 7:38 ` Chung-Lin Tang
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).