This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Committed] PR25600: Optimize (X>>31)!=0 and -(X<0).
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 17 Feb 2006 22:22:28 -0700 (MST)
- Subject: [Committed] PR25600: Optimize (X>>31)!=0 and -(X<0).
This patch implements two sets of transformations to resolve PR
middle-end/25600. The first set of transformations is at the
tree-level to transform "(X>>C) != 0" and "(X>>C) == 0" into
"X < 0" and "X >= 0" respectively, when C is one less that the
width of X. In these cases, the shift is effectively a sign bit
test which can be canonicalized to a comparison against zero.
A test against zero is cheaper than a shift and a test against
zero!
The second set of transformations is in the RTL optimizers to
convert (NEG (LT x 0)) into either (ASHIFTRT x C) or (LSHIFTRT x C),
where C is one less than the width of x, depending upon the backend
definition of store flag value. The RTL optimizers already contain
transformations such that (NEG (ASHIFTRT x 31)) -> (LSHIFTRT x 31)
and (NEG (LSHIFTRT x 31)) -> (ASHIFTRT x 31). Unfortunately, RTL
simplification may turn these shifts into comparisons against zero
[like we now do in fold!], so we extend these transformations to
recognize the transformed form.
Whilst bootstrapping and regression testing this patch, which now
produces optimal code for all the examples in PR25600, I realized
that this latter optimization could/should also be implemented at
the tree-level. I'm preparing a follow-up patch.
The patch below has been bootstraped and regression tested on
x86_64-unknown-linux-gnu, all default languages, with no new
failures. A test case would be complicated by the dependency
on target type widths.
Committed to mainline as revision 111226.
2006-02-17 Roger Sayle <roger@eyesopen.com>
PR middle-end/25600
* fold-const.c (fold_binary): Fold (X >> C) != 0 into X < 0 when
C is one less than the width of X (and related transformations).
* simplify_rtx.c (simplify_unary_operation_1): Transform
(neg (lt x 0)) into either (ashiftrt X C) or (lshiftrt X C)
depending on STORE_FLAG_VALUE, were C is one less then the
width of X.
Index: fold-const.c
===================================================================
*** fold-const.c (revision 110775)
--- fold-const.c (working copy)
*************** fold_binary (enum tree_code code, tree t
*** 9945,9950 ****
--- 9945,9974 ----
return t1;
}
+ /* Fold (X >> C) != 0 into X < 0 if C is one less than the width
+ of X. Similarly fold (X >> C) == 0 into X >= 0. */
+ if ((code == EQ_EXPR || code == NE_EXPR)
+ && integer_zerop (arg1)
+ && TREE_CODE (arg0) == RSHIFT_EXPR
+ && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
+ {
+ tree arg00 = TREE_OPERAND (arg0, 0);
+ tree arg01 = TREE_OPERAND (arg0, 1);
+ tree itype = TREE_TYPE (arg00);
+ if (TREE_INT_CST_HIGH (arg01) == 0
+ && TREE_INT_CST_LOW (arg01)
+ == (unsigned HOST_WIDE_INT) (TYPE_PRECISION (itype) - 1))
+ {
+ if (TYPE_UNSIGNED (itype))
+ {
+ itype = lang_hooks.types.signed_type (itype);
+ arg00 = fold_convert (itype, arg00);
+ }
+ return fold_build2 (code == EQ_EXPR ? GE_EXPR : LT_EXPR,
+ type, arg00, build_int_cst (itype, 0));
+ }
+ }
+
if ((code == EQ_EXPR || code == NE_EXPR)
&& integer_zerop (arg1)
&& tree_expr_nonzero_p (arg0))
Index: simplify-rtx.c
===================================================================
*** simplify-rtx.c (revision 110775)
--- simplify-rtx.c (working copy)
*************** simplify_unary_operation_1 (enum rtx_cod
*** 584,589 ****
--- 584,602 ----
&& XEXP (op, 1) == const1_rtx
&& nonzero_bits (XEXP (op, 0), mode) == 1)
return plus_constant (XEXP (op, 0), -1);
+
+ /* (neg (lt x 0)) is (ashiftrt X C) if STORE_FLAG_VALUE is 1. */
+ /* (neg (lt x 0)) is (lshiftrt X C) if STORE_FLAG_VALUE is -1. */
+ if (GET_CODE (op) == LT
+ && XEXP (op, 1) == const0_rtx)
+ {
+ if (STORE_FLAG_VALUE == 1)
+ return simplify_gen_binary (ASHIFTRT, mode, XEXP (op, 0),
+ GEN_INT (GET_MODE_BITSIZE (mode) - 1));
+ else if (STORE_FLAG_VALUE == -1)
+ return simplify_gen_binary (LSHIFTRT, mode, XEXP (op, 0),
+ GEN_INT (GET_MODE_BITSIZE (mode) - 1));
+ }
break;
case TRUNCATE:
Roger
--