[Committed] Optimize -((int)x>>31) as (unsigned int)x>>31
Roger Sayle
roger@eyesopen.com
Thu Mar 11 18:07:00 GMT 2004
I've committed the following patch to mainline CVS to add additional
transformations to constant folding and RTL simplification. These
optimizations were inspired by Andrew Pinski's "gzip trick" posting.
The negation of a shift to extract the sign bit of an integer, can
be simplified into just the shift of opposite signedness. Hence,
"-((int)x >> 31)" is equivalent to "(unsigned)x >> 31" and inversely
"-((unsigned)x >> 31" is equivalent to "(int)x >> 31", which avoids
the negation. The costs of arithmetic and logical right shifts are
typically the same, but even when not the difference is usually less
than the cost of the additional negation.
The following patch implements this optimization both at the tree-level
using "fold" and for RTL simplification in simplify_unary_operation.
This patch was tested on i686-pc-linux-gnu with a complete bootstrap
and regression tested with no new failures.
2004-03-11 Roger Sayle <roger@eyesopen.com>
* fold-const.c (negate_expr_p) <RSHIFT_EXPR>: We can optimize
-((int)X>>C) where C is an integer constant one bit less than the
size of X into (unsigned)X>>C. Similarly for unsigned->signed.
(negate_expr) <RSHIFT_EXPR>: Implement the above transformations.
* simplify-rtx.c (simplify_unary_operation): Also implement the
above transformations at the RTL level.
* gcc.c-torture/execute/20040311-1.c: New test case.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.342
diff -c -3 -p -r1.342 fold-const.c
*** fold-const.c 8 Mar 2004 01:55:44 -0000 1.342
--- fold-const.c 11 Mar 2004 00:09:40 -0000
*************** negate_expr_p (tree t)
*** 920,925 ****
--- 920,937 ----
return negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1)));
break;
+ case RSHIFT_EXPR:
+ /* Optimize -((int)x >> 31) into (unsigned)x >> 31. */
+ if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
+ {
+ tree op1 = TREE_OPERAND (t, 1);
+ if (TREE_INT_CST_HIGH (op1) == 0
+ && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
+ == TREE_INT_CST_LOW (op1))
+ return true;
+ }
+ break;
+
default:
break;
}
*************** negate_expr (tree t)
*** 1062,1067 ****
--- 1074,1098 ----
arg = negate_expr (TREE_VALUE (TREE_OPERAND (t, 1)));
arglist = build_tree_list (NULL_TREE, arg);
return build_function_call_expr (fndecl, arglist);
+ }
+ break;
+
+ case RSHIFT_EXPR:
+ /* Optimize -((int)x >> 31) into (unsigned)x >> 31. */
+ if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
+ {
+ tree op1 = TREE_OPERAND (t, 1);
+ if (TREE_INT_CST_HIGH (op1) == 0
+ && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
+ == TREE_INT_CST_LOW (op1))
+ {
+ tree ntype = TREE_UNSIGNED (type)
+ ? (*lang_hooks.types.signed_type) (type)
+ : (*lang_hooks.types.unsigned_type) (type);
+ tree temp = fold_convert (ntype, TREE_OPERAND (t, 0));
+ temp = fold (build2 (RSHIFT_EXPR, ntype, temp, op1));
+ return fold_convert (type, temp);
+ }
}
break;
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.181
diff -c -3 -p -r1.181 simplify-rtx.c
*** simplify-rtx.c 9 Mar 2004 17:06:21 -0000 1.181
--- simplify-rtx.c 11 Mar 2004 00:09:41 -0000
*************** simplify_unary_operation (enum rtx_code
*** 1013,1018 ****
--- 1013,1034 ----
XEXP (op, 1));
}
+ /* (neg (ashiftrt X C)) can be replaced by (lshiftrt X C) when
+ C is equal to the width of MODE minus 1. */
+ if (GET_CODE (op) == ASHIFTRT
+ && GET_CODE (XEXP (op, 1)) == CONST_INT
+ && INTVAL (XEXP (op, 1)) == GET_MODE_BITSIZE (mode) - 1)
+ return simplify_gen_binary (LSHIFTRT, mode,
+ XEXP (op, 0), XEXP (op, 1));
+
+ /* (neg (lshiftrt X C)) can be replaced by (ashiftrt X C) when
+ C is equal to the width of MODE minus 1. */
+ if (GET_CODE (op) == LSHIFTRT
+ && GET_CODE (XEXP (op, 1)) == CONST_INT
+ && INTVAL (XEXP (op, 1)) == GET_MODE_BITSIZE (mode) - 1)
+ return simplify_gen_binary (ASHIFTRT, mode,
+ XEXP (op, 0), XEXP (op, 1));
+
break;
case SIGN_EXTEND:
/* Copyright (C) 2004 Free Software Foundation.
Check that constant folding and RTL simplification of -(x >> y) doesn't
break anything and produces the expected results.
Written by Roger Sayle, 11th March 2004. */
extern void abort (void);
#define INT_BITS (sizeof(int)*8)
int test1(int x)
{
return -(x >> (INT_BITS-1));
}
int test2(unsigned int x)
{
return -((int)(x >> (INT_BITS-1)));
}
int test3(int x)
{
int y;
y = INT_BITS-1;
return -(x >> y);
}
int test4(unsigned int x)
{
int y;
y = INT_BITS-1;
return -((int)(x >> y));
}
int main()
{
if (test1(0) != 0)
abort ();
if (test1(1) != 0)
abort ();
if (test1(-1) != 1)
abort ();
if (test2(0) != 0)
abort ();
if (test2(1) != 0)
abort ();
if (test2((unsigned int)-1) != -1)
abort ();
if (test3(0) != 0)
abort ();
if (test3(1) != 0)
abort ();
if (test3(-1) != 1)
abort ();
if (test4(0) != 0)
abort ();
if (test4(1) != 0)
abort ();
if (test4((unsigned int)-1) != -1)
abort ();
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
More information about the Gcc-patches
mailing list