[PATCH] Constant fold "bitop" builtins at the tree-level.
Roger Sayle
roger@eyesopen.com
Mon Aug 25 03:16:00 GMT 2003
The following patch allows us to evaluate ffs of a constant integer
argument in "fold". It also handles the other "bitop" builtins:
__builtin_clz, __builtin_ctz, __builtin_popcount and __builtin_parity,
and their long and long long variants (e.g. ffsl and ffsll). We can
currently evaluate these intrinsics during RTL simplification, but
constant folding them earlier can enable other optimizations and helps
the tree-ssa optimizers.
Whilst I was working on this patch, I also noticed that the CONST_DOUBLE
forms of the CLZ and CTZ RTL simplifiers weren't honoring the target
macros CLZ_DEFINED_VALUE_AT_ZERO and CTZ_DEFINED_VALUE_AT_ZERO. These
macros are already being honored in the CONST_INT RTL simplifiers.
The following patch has been 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. This functionality
is already heavily tested by gcc.c-torture/execute/builtin-bitops-1.c.
Ok for mainline?
2003-08-24 Roger Sayle <roger@eyesopen.com>
* builtins.c (fold_builtin_bitop): New function to perform constant
folding of ffs, clz, ctz, popcount and parity builtin functions and
their long and long long variants (such as ffsl and ffsll).
(fold_builtin): fold_builtin_bitop when appropriate.
* simplify-rtx.c (simplify_unary_operation): Honor both
CLZ_DEFINED_VALUE_AT_ZERO and CTZ_DEFINED_VALUE_AT_ZERO when
evaluating the CONST_DOUBLE forms of clz and ctz at compile-time.
Index: builtins.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/builtins.c,v
retrieving revision 1.240
diff -c -3 -p -r1.240 builtins.c
*** builtins.c 20 Aug 2003 19:27:49 -0000 1.240
--- builtins.c 24 Aug 2003 21:18:42 -0000
*************** static tree fold_builtin_cabs (tree, tre
*** 162,167 ****
--- 162,168 ----
static tree fold_builtin_trunc (tree);
static tree fold_builtin_floor (tree);
static tree fold_builtin_ceil (tree);
+ static tree fold_builtin_bitop (tree);
/* Initialize mathematical constants for constant folding builtins.
These constants need to be given to at least 160 bits precision. */
*************** fold_builtin_ceil (tree exp)
*** 5726,5731 ****
--- 5727,5840 ----
return fold_trunc_transparent_mathfn (exp);
}
+ /* Fold function call to builtin ffs, clz, ctz, popcount and parity
+ and their long and long long variants (i.e. ffsl and ffsll).
+ Return NULL_TREE if no simplification can be made. */
+
+ static tree
+ fold_builtin_bitop (tree exp)
+ {
+ tree fndecl = get_callee_fndecl (exp);
+ tree arglist = TREE_OPERAND (exp, 1);
+ tree arg;
+
+ if (! validate_arglist (arglist, INTEGER_TYPE, VOID_TYPE))
+ return NULL_TREE;
+
+ /* Optimize for constant argument. */
+ arg = TREE_VALUE (arglist);
+ if (TREE_CODE (arg) == INTEGER_CST && ! TREE_CONSTANT_OVERFLOW (arg))
+ {
+ HOST_WIDE_INT hi, width, result;
+ unsigned HOST_WIDE_INT lo;
+ tree type, t;
+
+ type = TREE_TYPE (arg);
+ width = TYPE_PRECISION (type);
+ lo = TREE_INT_CST_LOW (arg);
+
+ /* Clear all the bits that are beyond the type's precision. */
+ if (width > HOST_BITS_PER_WIDE_INT)
+ {
+ hi = TREE_INT_CST_HIGH (arg);
+ if (width < 2 * HOST_BITS_PER_WIDE_INT)
+ hi &= ~((HOST_WIDE_INT) (-1) >> (width - HOST_BITS_PER_WIDE_INT));
+ }
+ else
+ {
+ hi = 0;
+ if (width < HOST_BITS_PER_WIDE_INT)
+ lo &= ~((unsigned HOST_WIDE_INT) (-1) << width);
+ }
+
+ switch (DECL_FUNCTION_CODE (fndecl))
+ {
+ case BUILT_IN_FFS:
+ case BUILT_IN_FFSL:
+ case BUILT_IN_FFSLL:
+ if (lo != 0)
+ result = exact_log2 (lo & -lo) + 1;
+ else if (hi != 0)
+ result = HOST_BITS_PER_WIDE_INT + exact_log2 (hi & -hi) + 1;
+ else
+ result = 0;
+ break;
+
+ case BUILT_IN_CLZ:
+ case BUILT_IN_CLZL:
+ case BUILT_IN_CLZLL:
+ if (hi != 0)
+ result = width - floor_log2 (hi) - 1 - HOST_BITS_PER_WIDE_INT;
+ else if (lo != 0)
+ result = width - floor_log2 (lo) - 1;
+ else if (! CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (type), result))
+ result = width;
+ break;
+
+ case BUILT_IN_CTZ:
+ case BUILT_IN_CTZL:
+ case BUILT_IN_CTZLL:
+ if (lo != 0)
+ result = exact_log2 (lo & -lo);
+ else if (hi != 0)
+ result = HOST_BITS_PER_WIDE_INT + exact_log2 (hi & -hi);
+ else if (! CTZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (type), result))
+ result = width;
+ break;
+
+ case BUILT_IN_POPCOUNT:
+ case BUILT_IN_POPCOUNTL:
+ case BUILT_IN_POPCOUNTLL:
+ result = 0;
+ while (lo)
+ result++, lo &= lo - 1;
+ while (hi)
+ result++, hi &= hi - 1;
+ break;
+
+ case BUILT_IN_PARITY:
+ case BUILT_IN_PARITYL:
+ case BUILT_IN_PARITYLL:
+ result = 0;
+ while (lo)
+ result++, lo &= lo - 1;
+ while (hi)
+ result++, hi &= hi - 1;
+ result &= 1;
+ break;
+
+ default:
+ abort();
+ }
+
+ t = build_int_2 (result, 0);
+ TREE_TYPE (t) = TREE_TYPE (exp);
+ return t;
+ }
+
+ return NULL_TREE;
+ }
+
/* Used by constant folding to eliminate some builtin calls early. EXP is
the CALL_EXPR of a call to a builtin function. */
*************** fold_builtin (tree exp)
*** 6180,6185 ****
--- 6289,6311 ----
case BUILT_IN_NEARBYINTF:
case BUILT_IN_NEARBYINTL:
return fold_trunc_transparent_mathfn (exp);
+
+ case BUILT_IN_FFS:
+ case BUILT_IN_FFSL:
+ case BUILT_IN_FFSLL:
+ case BUILT_IN_CLZ:
+ case BUILT_IN_CLZL:
+ case BUILT_IN_CLZLL:
+ case BUILT_IN_CTZ:
+ case BUILT_IN_CTZL:
+ case BUILT_IN_CTZLL:
+ case BUILT_IN_POPCOUNT:
+ case BUILT_IN_POPCOUNTL:
+ case BUILT_IN_POPCOUNTLL:
+ case BUILT_IN_PARITY:
+ case BUILT_IN_PARITYL:
+ case BUILT_IN_PARITYLL:
+ return fold_builtin_bitop (exp);
default:
break;
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.155
diff -c -3 -p -r1.155 simplify-rtx.c
*** simplify-rtx.c 22 Aug 2003 06:25:08 -0000 1.155
--- simplify-rtx.c 24 Aug 2003 21:18:43 -0000
*************** simplify_unary_operation (enum rtx_code
*** 649,672 ****
case CLZ:
hv = 0;
! if (h1 == 0)
! lv = GET_MODE_BITSIZE (mode) - floor_log2 (l1) - 1;
! else
lv = GET_MODE_BITSIZE (mode) - floor_log2 (h1) - 1
- HOST_BITS_PER_WIDE_INT;
break;
case CTZ:
hv = 0;
! if (l1 == 0)
! {
! if (h1 == 0)
! lv = GET_MODE_BITSIZE (mode);
! else
! lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & -h1);
! }
! else
lv = exact_log2 (l1 & -l1);
break;
case POPCOUNT:
--- 649,671 ----
case CLZ:
hv = 0;
! if (h1 != 0)
lv = GET_MODE_BITSIZE (mode) - floor_log2 (h1) - 1
- HOST_BITS_PER_WIDE_INT;
+ else if (l1 != 0)
+ lv = GET_MODE_BITSIZE (mode) - floor_log2 (l1) - 1;
+ else if (! CLZ_DEFINED_VALUE_AT_ZERO (mode, lv))
+ lv = GET_MODE_BITSIZE (mode);
break;
case CTZ:
hv = 0;
! if (l1 != 0)
lv = exact_log2 (l1 & -l1);
+ else if (h1 != 0)
+ lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & -h1);
+ else if (! CTZ_DEFINED_VALUE_AT_ZERO (mode, lv))
+ lv = GET_MODE_BITSIZE (mode);
break;
case POPCOUNT:
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