This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Committed] Canonicalize XOR of sign-bit as addition
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 9 Apr 2004 14:38:15 -0600 (MDT)
- Subject: [Committed] Canonicalize XOR of sign-bit as addition
As pointed out by Segher Boessenkool, GCC currently fails to simplify
the following code.
> int foo (int x)
> {
> return ((x & 0xffffffff) ^ 0x80000000) - 0x80000000;
> }
I believe the correct approach is to recognize that "x ^ 0x80000000",
"x + 0x80000000" and "x - 0x80000000" all represent same operation and
should be canonicalized to the same thing. My preference is to use the
addition as the preferred canonical form: (i) there are far more
optimizations of plus than there are for xor, (ii) many architectures
may perform multiple additions in a single cycle, or even a single
instruction but fewer handle multiple xors and (iii) GCC already
canonicalizes misnus of the "sign bit" or "most significant bit"
into an addition.
To avoid loosing any optimization opportunties converting this XOR
into a PLUS, the patch below adds compensating optimizations that allow
us to optimize the additions as though they were XORs, for example
combining/associating suitable additions with other XORs.
The following patch and 3 new testcases were tested on i686-pc-linux-gnu
with a complete "make bootstrap", all languages except treelang, and
regression tested with a top-level "make -k check" with no new failures.
Committed to mainline CVS.
2004-04-09 Roger Sayle <roger@eyesopen.com>
* simplify-rtx.c (mode_signbit_p): New function to check whether
an RTX is an immediate constant that represents the most significant
bit of a given machine mode.
(simplify_unary_operation) <NOT>: Optimize ~(X+C) as X ^ ~C, where
C is the sign bit.
(simplify_binary_operation) <PLUS>: Optimize (X^C1) + C2 as X^(C1^C2)
when C2 is the sign bit.
(simplify_binary_operation) <XOR>: Canonicalize X^C as X+C when C
is the sign bit. Optimize (X+C1) ^ C2 as X^(C1^C2) when C1 is the
sign bit.
* gcc.c-torture/execute/20040409-1.c: New test case.
* gcc.c-torture/execute/20040409-2.c: New test case.
* gcc.c-torture/execute/20040409-3.c: New test case.
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.185
diff -c -3 -p -r1.185 simplify-rtx.c
*** simplify-rtx.c 5 Apr 2004 03:14:13 -0000 1.185
--- simplify-rtx.c 9 Apr 2004 17:02:41 -0000
*************** Software Foundation, 59 Temple Place - S
*** 50,55 ****
--- 50,56 ----
((((HOST_WIDE_INT) low) < 0) ? ((HOST_WIDE_INT) -1) : ((HOST_WIDE_INT) 0))
static rtx neg_const_int (enum machine_mode, rtx);
+ static bool mode_signbit_p (enum machine_mode, rtx);
static int simplify_plus_minus_op_data_cmp (const void *, const void *);
static rtx simplify_plus_minus (enum rtx_code, enum machine_mode, rtx,
rtx, int);
*************** neg_const_int (enum machine_mode mode, r
*** 66,71 ****
--- 67,105 ----
return gen_int_mode (- INTVAL (i), mode);
}
+ /* Test whether expression, X, is an immediate constant that represents
+ the most significant bit of machine mode MODE. */
+
+ static bool
+ mode_signbit_p (enum machine_mode mode, rtx x)
+ {
+ unsigned HOST_WIDE_INT val;
+ unsigned int width;
+
+ if (GET_MODE_CLASS (mode) != MODE_INT)
+ return false;
+
+ width = GET_MODE_BITSIZE (mode);
+ if (width == 0)
+ return false;
+
+ if (width <= HOST_BITS_PER_WIDE_INT
+ && GET_CODE (x) == CONST_INT)
+ val = INTVAL (x);
+ else if (width <= 2 * HOST_BITS_PER_WIDE_INT
+ && GET_CODE (x) == CONST_DOUBLE
+ && CONST_DOUBLE_LOW (x) == 0)
+ {
+ val = CONST_DOUBLE_HIGH (x);
+ width -= HOST_BITS_PER_WIDE_INT;
+ }
+ else
+ return false;
+
+ if (width < HOST_BITS_PER_WIDE_INT)
+ val &= ((unsigned HOST_WIDE_INT) 1 << width) - 1;
+ return val == ((unsigned HOST_WIDE_INT) 1 << (width - 1));
+ }
/* Make a binary operation by properly ordering the operands and
seeing if the expression folds. */
*************** simplify_unary_operation (enum rtx_code
*** 912,917 ****
--- 946,961 ----
mode)) != 0)
return simplify_gen_binary (XOR, mode, XEXP (op, 0), temp);
+ /* (not (plus X C)) for signbit C is (xor X D) with D = ~C. */
+ if (GET_CODE (op) == PLUS
+ && GET_CODE (XEXP (op, 1)) == CONST_INT
+ && mode_signbit_p (mode, XEXP (op, 1))
+ && (temp = simplify_unary_operation (NOT, mode,
+ XEXP (op, 1),
+ mode)) != 0)
+ return simplify_gen_binary (XOR, mode, XEXP (op, 0), temp);
+
+
/* (not (ashift 1 X)) is (rotate ~1 X). We used to do this for
operands other than 1, but that is not valid. We could do a
*************** simplify_binary_operation (enum rtx_code
*** 1514,1519 ****
--- 1558,1574 ----
}
}
+ /* (plus (xor X C1) C2) is (xor X (C1^C2)) if C2 is signbit. */
+ if ((GET_CODE (op1) == CONST_INT
+ || GET_CODE (op1) == CONST_DOUBLE)
+ && GET_CODE (op0) == XOR
+ && (GET_CODE (XEXP (op0, 1)) == CONST_INT
+ || GET_CODE (XEXP (op0, 1)) == CONST_DOUBLE)
+ && mode_signbit_p (mode, op1))
+ return simplify_gen_binary (XOR, mode, XEXP (op0, 0),
+ simplify_gen_binary (XOR, mode, op1,
+ XEXP (op0, 1)));
+
/* If one of the operands is a PLUS or a MINUS, see if we can
simplify this by the associative law.
Don't use the associative law for floating point.
*************** simplify_binary_operation (enum rtx_code
*** 1797,1805 ****
&& ((INTVAL (trueop1) & GET_MODE_MASK (mode))
== GET_MODE_MASK (mode)))
return simplify_gen_unary (NOT, mode, op0, mode);
! if (trueop0 == trueop1 && ! side_effects_p (op0)
&& GET_MODE_CLASS (mode) != MODE_CC)
return const0_rtx;
tem = simplify_associative_operation (code, mode, op0, op1);
if (tem)
return tem;
--- 1852,1878 ----
&& ((INTVAL (trueop1) & GET_MODE_MASK (mode))
== GET_MODE_MASK (mode)))
return simplify_gen_unary (NOT, mode, op0, mode);
! if (trueop0 == trueop1
! && ! side_effects_p (op0)
&& GET_MODE_CLASS (mode) != MODE_CC)
return const0_rtx;
+
+ /* Canonicalize XOR of the most significant bit to PLUS. */
+ if ((GET_CODE (op1) == CONST_INT
+ || GET_CODE (op1) == CONST_DOUBLE)
+ && mode_signbit_p (mode, op1))
+ return simplify_gen_binary (PLUS, mode, op0, op1);
+ /* (xor (plus X C1) C2) is (xor X (C1^C2)) if C1 is signbit. */
+ if ((GET_CODE (op1) == CONST_INT
+ || GET_CODE (op1) == CONST_DOUBLE)
+ && GET_CODE (op0) == PLUS
+ && (GET_CODE (XEXP (op0, 1)) == CONST_INT
+ || GET_CODE (XEXP (op0, 1)) == CONST_DOUBLE)
+ && mode_signbit_p (mode, XEXP (op0, 1)))
+ return simplify_gen_binary (XOR, mode, XEXP (op0, 0),
+ simplify_gen_binary (XOR, mode, op1,
+ XEXP (op0, 1)));
+
tem = simplify_associative_operation (code, mode, op0, op1);
if (tem)
return tem;
#include <limits.h>
extern void abort ();
int test1(int x)
{
return x ^ INT_MIN;
}
unsigned int test1u(unsigned int x)
{
return x ^ (unsigned int)INT_MIN;
}
int test2(int x)
{
return x + INT_MIN;
}
unsigned int test2u(unsigned int x)
{
return x + (unsigned int)INT_MIN;
}
int test3(int x)
{
return x - INT_MIN;
}
unsigned int test3u(unsigned int x)
{
return x - (unsigned int)INT_MIN;
}
int test4(int x)
{
int y = INT_MIN;
return x ^ y;
}
unsigned int test4u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
return x ^ y;
}
int test5(int x)
{
int y = INT_MIN;
return x + y;
}
unsigned int test5u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
return x + y;
}
int test6(int x)
{
int y = INT_MIN;
return x - y;
}
unsigned int test6u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
return x - y;
}
void test(int a, int b)
{
if (test1(a) != b)
abort();
if (test2(a) != b)
abort();
if (test3(a) != b)
abort();
if (test4(a) != b)
abort();
if (test5(a) != b)
abort();
if (test6(a) != b)
abort();
}
void testu(unsigned int a, unsigned int b)
{
if (test1u(a) != b)
abort();
if (test2u(a) != b)
abort();
if (test3u(a) != b)
abort();
if (test4u(a) != b)
abort();
if (test5u(a) != b)
abort();
if (test6u(a) != b)
abort();
}
int main()
{
#if INT_MAX == 2147483647
test(0x00000000,0x80000000);
test(0x80000000,0x00000000);
test(0x12345678,0x92345678);
test(0x92345678,0x12345678);
test(0x7fffffff,0xffffffff);
test(0xffffffff,0x7fffffff);
testu(0x00000000,0x80000000);
testu(0x80000000,0x00000000);
testu(0x12345678,0x92345678);
testu(0x92345678,0x12345678);
testu(0x7fffffff,0xffffffff);
testu(0xffffffff,0x7fffffff);
#endif
#if INT_MAX == 32767
test(0x0000,0x8000);
test(0x8000,0x0000);
test(0x1234,0x9234);
test(0x9234,0x1234);
test(0x7fff,0xffff);
test(0xffff,0x7fff);
testu(0x0000,0x8000);
testu(0x8000,0x0000);
testu(0x1234,0x9234);
testu(0x9234,0x1234);
testu(0x7fff,0xffff);
testu(0xffff,0x7fff);
#endif
return 0;
}
#include <limits.h>
extern void abort ();
int test1(int x)
{
return (x ^ INT_MIN) ^ 0x1234;
}
unsigned int test1u(unsigned int x)
{
return (x ^ (unsigned int)INT_MIN) ^ 0x1234;
}
int test2(int x)
{
return (x ^ 0x1234) ^ INT_MIN;
}
unsigned int test2u(unsigned int x)
{
return (x ^ 0x1234) ^ (unsigned int)INT_MIN;
}
int test3(int x)
{
return (x + INT_MIN) ^ 0x1234;
}
unsigned int test3u(unsigned int x)
{
return (x + (unsigned int)INT_MIN) ^ 0x1234;
}
int test4(int x)
{
return (x ^ 0x1234) + INT_MIN;
}
unsigned int test4u(unsigned int x)
{
return (x ^ 0x1234) + (unsigned int)INT_MIN;
}
int test5(int x)
{
return (x - INT_MIN) ^ 0x1234;
}
unsigned int test5u(unsigned int x)
{
return (x - (unsigned int)INT_MIN) ^ 0x1234;
}
int test6(int x)
{
return (x ^ 0x1234) - INT_MIN;
}
unsigned int test6u(unsigned int x)
{
return (x ^ 0x1234) - (unsigned int)INT_MIN;
}
int test7(int x)
{
int y = INT_MIN;
int z = 0x1234;
return (x ^ y) ^ z;
}
unsigned int test7u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
unsigned int z = 0x1234;
return (x ^ y) ^ z;
}
int test8(int x)
{
int y = 0x1234;
int z = INT_MIN;
return (x ^ y) ^ z;
}
unsigned int test8u(unsigned int x)
{
unsigned int y = 0x1234;
unsigned int z = (unsigned int)INT_MIN;
return (x ^ y) ^ z;
}
int test9(int x)
{
int y = INT_MIN;
int z = 0x1234;
return (x + y) ^ z;
}
unsigned int test9u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
unsigned int z = 0x1234;
return (x + y) ^ z;
}
int test10(int x)
{
int y = 0x1234;
int z = INT_MIN;
return (x ^ y) + z;
}
unsigned int test10u(unsigned int x)
{
unsigned int y = 0x1234;
unsigned int z = (unsigned int)INT_MIN;
return (x ^ y) + z;
}
int test11(int x)
{
int y = INT_MIN;
int z = 0x1234;
return (x - y) ^ z;
}
unsigned int test11u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
unsigned int z = 0x1234;
return (x - y) ^ z;
}
int test12(int x)
{
int y = 0x1234;
int z = INT_MIN;
return (x ^ y) - z;
}
unsigned int test12u(unsigned int x)
{
unsigned int y = 0x1234;
unsigned int z = (unsigned int)INT_MIN;
return (x ^ y) - z;
}
void test(int a, int b)
{
if (test1(a) != b)
abort();
if (test2(a) != b)
abort();
if (test3(a) != b)
abort();
if (test4(a) != b)
abort();
if (test5(a) != b)
abort();
if (test6(a) != b)
abort();
if (test7(a) != b)
abort();
if (test8(a) != b)
abort();
if (test9(a) != b)
abort();
if (test10(a) != b)
abort();
if (test11(a) != b)
abort();
if (test12(a) != b)
abort();
}
void testu(unsigned int a, unsigned int b)
{
if (test1u(a) != b)
abort();
if (test2u(a) != b)
abort();
if (test3u(a) != b)
abort();
if (test4u(a) != b)
abort();
if (test5u(a) != b)
abort();
if (test6u(a) != b)
abort();
if (test7u(a) != b)
abort();
if (test8u(a) != b)
abort();
if (test9u(a) != b)
abort();
if (test10u(a) != b)
abort();
if (test11u(a) != b)
abort();
if (test12u(a) != b)
abort();
}
int main()
{
#if INT_MAX == 2147483647
test(0x00000000,0x80001234);
test(0x00001234,0x80000000);
test(0x80000000,0x00001234);
test(0x80001234,0x00000000);
test(0x7fffffff,0xffffedcb);
test(0xffffffff,0x7fffedcb);
testu(0x00000000,0x80001234);
testu(0x00001234,0x80000000);
testu(0x80000000,0x00001234);
testu(0x80001234,0x00000000);
testu(0x7fffffff,0xffffedcb);
testu(0xffffffff,0x7fffedcb);
#endif
#if INT_MAX == 32767
test(0x0000,0x9234);
test(0x1234,0x8000);
test(0x8000,0x1234);
test(0x9234,0x0000);
test(0x7fff,0xffff);
test(0xffff,0x7fff);
testu(0x0000,0x8000);
testu(0x8000,0x0000);
testu(0x1234,0x9234);
testu(0x9234,0x1234);
testu(0x7fff,0xedcb);
testu(0xffff,0x6dcb);
#endif
return 0;
}
#include <limits.h>
extern void abort ();
int test1(int x)
{
return ~(x ^ INT_MIN);
}
unsigned int test1u(unsigned int x)
{
return ~(x ^ (unsigned int)INT_MIN);
}
int test2(int x)
{
return ~(x + INT_MIN);
}
unsigned int test2u(unsigned int x)
{
return ~(x + (unsigned int)INT_MIN);
}
int test3(int x)
{
return ~(x - INT_MIN);
}
unsigned int test3u(unsigned int x)
{
return ~(x - (unsigned int)INT_MIN);
}
int test4(int x)
{
int y = INT_MIN;
return ~(x ^ y);
}
unsigned int test4u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
return ~(x ^ y);
}
int test5(int x)
{
int y = INT_MIN;
return ~(x + y);
}
unsigned int test5u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
return ~(x + y);
}
int test6(int x)
{
int y = INT_MIN;
return ~(x - y);
}
unsigned int test6u(unsigned int x)
{
unsigned int y = (unsigned int)INT_MIN;
return ~(x - y);
}
void test(int a, int b)
{
if (test1(a) != b)
abort();
if (test2(a) != b)
abort();
if (test3(a) != b)
abort();
if (test4(a) != b)
abort();
if (test5(a) != b)
abort();
if (test6(a) != b)
abort();
}
void testu(unsigned int a, unsigned int b)
{
if (test1u(a) != b)
abort();
if (test2u(a) != b)
abort();
if (test3u(a) != b)
abort();
if (test4u(a) != b)
abort();
if (test5u(a) != b)
abort();
if (test6u(a) != b)
abort();
}
int main()
{
#if INT_MAX == 2147483647
test(0x00000000,0x7fffffff);
test(0x80000000,0xffffffff);
test(0x12345678,0x6dcba987);
test(0x92345678,0xedcba987);
test(0x7fffffff,0x00000000);
test(0xffffffff,0x80000000);
testu(0x00000000,0x7fffffff);
testu(0x80000000,0xffffffff);
testu(0x12345678,0x6dcba987);
testu(0x92345678,0xedcba987);
testu(0x7fffffff,0x00000000);
testu(0xffffffff,0x80000000);
#endif
#if INT_MAX == 32767
test(0x0000,0x7fff);
test(0x8000,0xffff);
test(0x1234,0x6dcb);
test(0x9234,0xedcb);
test(0x7fff,0x0000);
test(0xffff,0x8000);
testu(0x0000,0x7fff);
testu(0x8000,0xffff);
testu(0x1234,0x6dcb);
testu(0x9234,0xedcb);
testu(0x7fff,0x0000);
testu(0xffff,0x8000);
#endif
return 0;
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833