| Message ID | 4D7A2E4A.5070306@codesourcery.com |
|---|---|
| State | New |
| Headers | show |
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.
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~
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 |
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~
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" } } */
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.