This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Committed] Optimize X % -Y as X % Y and other tweaks
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 5 Jul 2004 10:47:54 -0600 (MDT)
- Subject: [Committed] Optimize X % -Y as X % Y and other tweaks
The following patch improves GCC's contant folding of the modulus
(remainder) operator.
Firstly, it adds support for converting "X % C" where the operator is
an unsigned TRUNC_MOD_EXPR, and C is a constant power of two, into
a BIT_AND_EXPR, "X & (C-1)". This optimization is already implemented
as an RTL optimization, but this "hunk" makes it visible to tree-ssa.
Next, we now optimize "X % -Y" as "X % Y", if we don't care about
trapping math. By my calculations this is correct for all rounding
*_MOD_EXPRs (including FLOOR_MOD_EXPR and CEIL_MOD_EXPR). This
transformation is also used to canonicalize modulus by an integer
constant to ensure that this second operand is always positive.
Hence X % -16 is normalized to X % 16, which under the correct
circumstances will catch the power-of-two transformations. Finally,
the EQ_EXPR/NE_EXPR section of fold is tweaked, such that the
transformation of a signed modulus into an unsigned modulus recursively
calls fold, so that "(X % -16) == 0" is reduced to a BIT_AND_EXPR,
even when X is signed.
The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all default languages, and regression tested with
a top-level "make -k check" with no new failures.
Committed to mainline CVS.
2004-07-05 Roger Sayle <roger@eyesopen.com>
* fold-const.c (fold) <TRUNC_MOD_EXPR>: Optimize unsigned modulus
by a power of two into a bit-wise AND, i.e. "X % C" as "X & (C-1)".
Normalize "X % C" as "X % -C" for signed modulus and negative C.
Optimize "X % -Y" as "X % Y" for signed modulus.
<EQ_EXPR>: Recursively call "fold" when transforming "(X % Y) == 0"
into "((unsigned) X % Y) == 0".
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.416
diff -c -3 -p -r1.416 fold-const.c
*** fold-const.c 3 Jul 2004 00:15:40 -0000 1.416
--- fold-const.c 5 Jul 2004 05:14:00 -0000
*************** fold (tree expr)
*** 7538,7543 ****
--- 7538,7544 ----
return omit_one_operand (type, integer_zero_node, arg0);
if (integer_zerop (arg1))
return t;
+
/* X % -1 is zero. */
if (!TYPE_UNSIGNED (type)
&& TREE_CODE (arg1) == INTEGER_CST
*************** fold (tree expr)
*** 7545,7550 ****
--- 7546,7597 ----
&& TREE_INT_CST_HIGH (arg1) == -1)
return omit_one_operand (type, integer_zero_node, arg0);
+ /* Optimize unsigned TRUNC_MOD_EXPR by a power of two into a
+ BIT_AND_EXPR, i.e. "X % C" into "X & C2". */
+ if (code == TRUNC_MOD_EXPR
+ && TYPE_UNSIGNED (type)
+ && integer_pow2p (arg1))
+ {
+ unsigned HOST_WIDE_INT high, low;
+ tree mask;
+ int l;
+
+ l = tree_log2 (arg1);
+ if (l >= HOST_BITS_PER_WIDE_INT)
+ {
+ high = ((unsigned HOST_WIDE_INT) 1
+ << (l - HOST_BITS_PER_WIDE_INT)) - 1;
+ low = -1;
+ }
+ else
+ {
+ high = 0;
+ low = ((unsigned HOST_WIDE_INT) 1 << l) - 1;
+ }
+
+ mask = build_int_2 (low, high);
+ TREE_TYPE (mask) = type;
+ return fold (build2 (BIT_AND_EXPR, type,
+ fold_convert (type, arg0), mask));
+ }
+
+ /* X % -C is the same as X % C (for all rounding moduli). */
+ if (!TYPE_UNSIGNED (type)
+ && TREE_CODE (arg1) == INTEGER_CST
+ && TREE_INT_CST_HIGH (arg1) < 0
+ && !flag_trapv
+ /* Avoid this transformation if C is INT_MIN, i.e. C == -C. */
+ && !sign_bit_p (arg1, arg1))
+ return fold (build2 (code, type, fold_convert (type, arg0),
+ fold_convert (type, negate_expr (arg1))));
+
+ /* X % -Y is the same as X % Y (for all rounding moduli). */
+ if (!TYPE_UNSIGNED (type)
+ && TREE_CODE (arg1) == NEGATE_EXPR
+ && !flag_trapv)
+ return fold (build2 (code, type, fold_convert (type, arg0),
+ fold_convert (type, TREE_OPERAND (arg1, 0))));
+
if (TREE_CODE (arg1) == INTEGER_CST
&& 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
code, NULL_TREE)))
*************** fold (tree expr)
*** 8268,8280 ****
&& integer_pow2p (TREE_OPERAND (arg0, 1)))
{
tree newtype = lang_hooks.types.unsigned_type (TREE_TYPE (arg0));
! tree newmod = build2 (TREE_CODE (arg0), newtype,
! fold_convert (newtype,
! TREE_OPERAND (arg0, 0)),
! fold_convert (newtype,
! TREE_OPERAND (arg0, 1)));
! return build2 (code, type, newmod, fold_convert (newtype, arg1));
}
/* If this is an NE comparison of zero with an AND of one, remove the
--- 8315,8328 ----
&& integer_pow2p (TREE_OPERAND (arg0, 1)))
{
tree newtype = lang_hooks.types.unsigned_type (TREE_TYPE (arg0));
! tree newmod = fold (build2 (TREE_CODE (arg0), newtype,
! fold_convert (newtype,
! TREE_OPERAND (arg0, 0)),
! fold_convert (newtype,
! TREE_OPERAND (arg0, 1))));
! return fold (build2 (code, type, newmod,
! fold_convert (newtype, arg1)));
}
/* If this is an NE comparison of zero with an AND of one, remove the
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