This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Bit twiddling builtins
On Wed, Feb 05, 2003 at 10:30:17AM +0000, Richard Earnshaw wrote:
> Can someone making use of the __builtin_clz builtin for ARM on gcc 3.2
> get the same behaviour now that we have the generic builtin of the same
> name without having to change their source. If not, then I don't think
> we can rename the builtin in this way.
Yes and no. That is, their source will continue to work on ARM5, but
they really ought to update it so that it'll work on other targets.
The main impetus for the following, however, is ARM's use of CLZ to
implement FFS. This allows there to be a defined value for CLZ(0)
at least within the compiler itself. It also addresses Geoff's
desire to be able to use (CTZ(x) >> 5) to implement (x == 0).
In addition, it fixes a couple of places where we'd intuit incorrect
possibilities when the value really is undefined, as for i386.
r~
* defaults.h (CLZ_DEFINED_VALUE_AT_ZERO): New.
(CTZ_DEFINED_VALUE_AT_ZERO): New.
* doc/rtl.texi, doc/tm.texi: Document them.
* combine.c (nonzero_bits) [CLZ, CTZ]: Handle the definedness
of the value at zero properly.
* fold-const.c (tree_expr_nonnegative_p): Likewise.
* simplify-rtx.c (simplify_unary_operation): Likewise.
* config/alpha/alpha.h (CLZ_DEFINED_VALUE_AT_ZERO): New.
(CTZ_DEFINED_VALUE_AT_ZERO): New.
* config/arm/arm.c (TARGET_INIT_BUILTINS): Remove.
(TARGET_EXPAND_BUILTIN): Remove.
(def_builtin, arm_init_builtins, arm_expand_builtin): Remove.
* config/arm/arm.h (CLZ_DEFINED_VALUE_AT_ZERO): New.
(enum arm_builtins): Remove.
* config/arm/arm.md (UNSPEC_CLZ): Remove.
(clzsi2): Rename from clz; use clz instead of unspec.
(ctzsi2): New.
* config/arm/arm-protos.h: Update.
Index: combine.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/combine.c,v
retrieving revision 1.335
diff -c -p -d -u -r1.335 combine.c
--- combine.c 1 Feb 2003 18:59:43 -0000 1.335
+++ combine.c 5 Feb 2003 22:20:37 -0000
@@ -8547,11 +8547,28 @@ nonzero_bits (x, mode)
break;
case FFS:
- case CLZ:
- case CTZ:
case POPCOUNT:
/* This is at most the number of bits in the mode. */
- nonzero = ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width) + 1)) - 1;
+ nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
+ break;
+
+ case CLZ:
+ /* If CLZ has a known value at zero, then the nonzero bits are
+ that value, plus the number of bits in the mode minus one. */
+ if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
+ nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
+ else
+ nonzero = -1;
+ break;
+
+ case CTZ:
+ /* If CTZ has a known value at zero, then the nonzero bits are
+ that value, plus the number of bits in the mode minus one. */
+ if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
+ nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
+ else
+ nonzero = -1;
+ break;
break;
case PARITY:
Index: defaults.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/defaults.h,v
retrieving revision 1.101
diff -c -p -d -u -r1.101 defaults.h
--- defaults.h 24 Jan 2003 22:07:00 -0000 1.101
+++ defaults.h 5 Feb 2003 22:20:37 -0000
@@ -644,4 +644,12 @@ You Lose! You must define PREFERRED_DEB
#define TARGET_C99_FUNCTIONS 0
#endif
+/* Indicate that CLZ and CTZ are undefined at zero. */
+#ifndef CLZ_DEFINED_VALUE_AT_ZERO
+#define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) 0
+#endif
+#ifndef CTZ_DEFINED_VALUE_AT_ZERO
+#define CTZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) 0
+#endif
+
#endif /* ! GCC_DEFAULTS_H */
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.233
diff -c -p -d -u -r1.233 fold-const.c
--- fold-const.c 1 Feb 2003 18:59:44 -0000 1.233
+++ fold-const.c 5 Feb 2003 22:20:38 -0000
@@ -7436,11 +7436,17 @@ tree_expr_nonnegative_p (t)
{
case ABS_EXPR:
case FFS_EXPR:
- case CLZ_EXPR:
- case CTZ_EXPR:
case POPCOUNT_EXPR:
case PARITY_EXPR:
return 1;
+
+ case CLZ_EXPR:
+ case CTZ_EXPR:
+ /* These are undefined at zero. This is true even if
+ C[LT]Z_DEFINED_VALUE_AT_ZERO is set, since what we're
+ computing here is a user-visible property. */
+ return 0;
+
case INTEGER_CST:
return tree_int_cst_sgn (t) >= 0;
case TRUNC_DIV_EXPR:
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.133
diff -c -p -d -u -r1.133 simplify-rtx.c
--- simplify-rtx.c 3 Feb 2003 19:40:57 -0000 1.133
+++ simplify-rtx.c 5 Feb 2003 22:20:38 -0000
@@ -449,14 +449,23 @@ simplify_unary_operation (code, mode, op
case CLZ:
arg0 &= GET_MODE_MASK (mode);
- val = GET_MODE_BITSIZE (mode) - floor_log2 (arg0) - 1;
+ if (arg0 == 0 && CLZ_DEFINED_VALUE_AT_ZERO (mode, val))
+ ;
+ else
+ val = GET_MODE_BITSIZE (mode) - floor_log2 (arg0) - 1;
break;
case CTZ:
arg0 &= GET_MODE_MASK (mode);
- val = arg0 == 0
- ? GET_MODE_BITSIZE (mode)
- : exact_log2 (arg0 & -arg0);
+ if (arg0 == 0)
+ {
+ /* Even if the value at zero is undefined, we have to come
+ up with some replacement. Seems good enough. */
+ if (! CTZ_DEFINED_VALUE_AT_ZERO (mode, val))
+ val = GET_MODE_BITSIZE (mode);
+ }
+ else
+ val = exact_log2 (arg0 & -arg0);
break;
case POPCOUNT:
Index: config/alpha/alpha.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/alpha/alpha.h,v
retrieving revision 1.191
diff -c -p -d -u -r1.191 alpha.h
--- config/alpha/alpha.h 31 Jan 2003 23:34:14 -0000 1.191
+++ config/alpha/alpha.h 5 Feb 2003 22:20:38 -0000
@@ -1493,6 +1493,10 @@ do { \
#define STORE_FLAG_VALUE 1
+/* The CIX ctlz and cttz instructions return 64 for zero. */
+#define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = 64, TARGET_CIX)
+#define CTZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = 64, TARGET_CIX)
+
/* Define the value returned by a floating-point comparison instruction. */
#define FLOAT_STORE_FLAG_VALUE(MODE) \
Index: config/arm/arm-protos.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/arm/arm-protos.h,v
retrieving revision 1.46
diff -c -p -d -u -r1.46 arm-protos.h
--- config/arm/arm-protos.h 29 Jan 2003 16:50:34 -0000 1.46
+++ config/arm/arm-protos.h 5 Feb 2003 22:20:38 -0000
@@ -209,12 +209,6 @@ extern void arm_mark_dllexport PARAMS
extern void arm_mark_dllimport PARAMS ((tree));
#endif
-extern void arm_init_builtins PARAMS ((void));
-#if defined (TREE_CODE) && defined (RTX_CODE)
-extern rtx arm_expand_builtin PARAMS ((tree, rtx, rtx,
- enum machine_mode, int));
-#endif
-
extern void arm_pr_long_calls PARAMS ((struct cpp_reader *));
extern void arm_pr_no_long_calls PARAMS ((struct cpp_reader *));
extern void arm_pr_long_calls_off PARAMS ((struct cpp_reader *));
Index: config/arm/arm.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/arm/arm.c,v
retrieving revision 1.256
diff -c -p -d -u -r1.256 arm.c
--- config/arm/arm.c 1 Feb 2003 18:59:52 -0000 1.256
+++ config/arm/arm.c 5 Feb 2003 22:20:38 -0000
@@ -187,12 +187,6 @@ static int arm_address_cost PARAMS ((r
#undef TARGET_SET_DEFAULT_TYPE_ATTRIBUTES
#define TARGET_SET_DEFAULT_TYPE_ATTRIBUTES arm_set_default_type_attributes
-#undef TARGET_INIT_BUILTINS
-#define TARGET_INIT_BUILTINS arm_init_builtins
-
-#undef TARGET_EXPAND_BUILTIN
-#define TARGET_EXPAND_BUILTIN arm_expand_builtin
-
#undef TARGET_SCHED_ADJUST_COST
#define TARGET_SCHED_ADJUST_COST arm_adjust_cost
@@ -9980,82 +9974,6 @@ arm_debugger_arg_offset (value, addr)
}
return value;
-}
-
-#define def_builtin(NAME, TYPE, CODE) \
- builtin_function ((NAME), (TYPE), (CODE), BUILT_IN_MD, NULL, NULL_TREE)
-
-void
-arm_init_builtins ()
-{
- tree endlink = void_list_node;
- tree int_endlink = tree_cons (NULL_TREE, integer_type_node, endlink);
- tree pchar_type_node = build_pointer_type (char_type_node);
-
- tree int_ftype_int, void_ftype_pchar;
-
- /* void func (char *) */
- void_ftype_pchar
- = build_function_type_list (void_type_node, pchar_type_node, NULL_TREE);
-
- /* int func (int) */
- int_ftype_int
- = build_function_type (integer_type_node, int_endlink);
-
- /* Initialize arm V5 builtins. */
- if (arm_arch5)
- def_builtin ("__builtin_arm_clz", int_ftype_int, ARM_BUILTIN_CLZ);
-}
-
-/* Expand an expression EXP that calls a built-in function,
- with result going to TARGET if that's convenient
- (and in mode MODE if that's convenient).
- SUBTARGET may be used as the target for computing one of EXP's operands.
- IGNORE is nonzero if the value is to be ignored. */
-
-rtx
-arm_expand_builtin (exp, target, subtarget, mode, ignore)
- tree exp;
- rtx target;
- rtx subtarget ATTRIBUTE_UNUSED;
- enum machine_mode mode ATTRIBUTE_UNUSED;
- int ignore ATTRIBUTE_UNUSED;
-{
- enum insn_code icode;
- tree fndecl = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
- tree arglist = TREE_OPERAND (exp, 1);
- tree arg0;
- rtx op0, pat;
- enum machine_mode tmode, mode0;
- int fcode = DECL_FUNCTION_CODE (fndecl);
-
- switch (fcode)
- {
- default:
- break;
-
- case ARM_BUILTIN_CLZ:
- icode = CODE_FOR_clz;
- arg0 = TREE_VALUE (arglist);
- op0 = expand_expr (arg0, NULL_RTX, VOIDmode, 0);
- tmode = insn_data[icode].operand[0].mode;
- mode0 = insn_data[icode].operand[1].mode;
-
- if (! (*insn_data[icode].operand[1].predicate) (op0, mode0))
- op0 = copy_to_mode_reg (mode0, op0);
- if (target == 0
- || GET_MODE (target) != tmode
- || ! (*insn_data[icode].operand[0].predicate) (target, tmode))
- target = gen_reg_rtx (tmode);
- pat = GEN_FCN (icode) (target, op0);
- if (! pat)
- return 0;
- emit_insn (pat);
- return target;
- }
-
- /* @@@ Should really do something sensible here. */
- return NULL_RTX;
}
/* Recursively search through all of the blocks in a function
Index: config/arm/arm.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/arm/arm.h,v
retrieving revision 1.180
diff -c -p -d -u -r1.180 arm.h
--- config/arm/arm.h 31 Jan 2003 02:20:48 -0000 1.180
+++ config/arm/arm.h 5 Feb 2003 22:20:38 -0000
@@ -2146,6 +2146,8 @@ extern int making_const_table;
#define STORE_FLAG_VALUE 1
+/* The arm5 clz instruction returns 32. */
+#define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = 32, 1)
/* Gcc puts the pool in the wrong place for ARM, since we can only
@@ -2456,9 +2458,4 @@ extern int making_const_table;
#define SPECIAL_MODE_PREDICATES \
"cc_register", "dominant_cc_register",
-enum arm_builtins
-{
- ARM_BUILTIN_CLZ,
- ARM_BUILTIN_MAX
-};
#endif /* ! GCC_ARM_H */
Index: config/arm/arm.md
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/arm/arm.md,v
retrieving revision 1.117
diff -c -p -d -u -r1.117 arm.md
--- config/arm/arm.md 2 Feb 2003 16:20:31 -0000 1.117
+++ config/arm/arm.md 5 Feb 2003 22:20:39 -0000
@@ -58,9 +58,6 @@
; value to it before trying to dereference it.
(UNSPEC_PRLG_STK 4) ; A special barrier that prevents frame accesses
; being scheduled before the stack adjustment insn.
- (UNSPEC_CLZ 5) ; `clz' instruction, count leading zeros (SImode):
- ; operand 0 is the result,
- ; operand 1 is the parameter.
(UNSPEC_PROLOGUE_USE 6) ; As USE insns are not meaningful after reload,
; this unspec is used to prevent the deletion of
; instructions setting registers for EH handling
@@ -8851,10 +8848,9 @@
;; V5 Instructions,
-(define_insn "clz"
- [(set (match_operand:SI 0 "s_register_operand" "=r")
- (unspec:SI [(match_operand:SI 1 "s_register_operand" "r")]
- UNSPEC_CLZ))]
+(define_insn "clzsi2"
+ [(set (match_operand:SI 0 "s_register_operand" "=r")
+ (clz:SI (match_operand:SI 1 "s_register_operand" "r")))]
"TARGET_ARM && arm_arch5"
"clz\\t%0, %1")
@@ -8872,8 +8868,28 @@
emit_insn (gen_negsi2 (t1, operands[1]));
emit_insn (gen_andsi3 (t2, operands[1], t1));
- emit_insn (gen_clz (t3, t2));
+ emit_insn (gen_clzsi2 (t3, t2));
emit_insn (gen_subsi3 (operands[0], GEN_INT (32), t3));
+ DONE;
+ }"
+)
+
+(define_expand "ctzsi2"
+ [(set (match_operand:SI 0 "s_register_operand" "")
+ (ctz:SI (match_operand:SI 1 "s_register_operand" "")))]
+ "TARGET_ARM && arm_arch5"
+ "
+ {
+ rtx t1, t2, t3;
+
+ t1 = gen_reg_rtx (SImode);
+ t2 = gen_reg_rtx (SImode);
+ t3 = gen_reg_rtx (SImode);
+
+ emit_insn (gen_negsi2 (t1, operands[1]));
+ emit_insn (gen_andsi3 (t2, operands[1], t1));
+ emit_insn (gen_clzsi2 (t3, t2));
+ emit_insn (gen_subsi3 (operands[0], GEN_INT (31), t3));
DONE;
}"
)
Index: doc/rtl.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/rtl.texi,v
retrieving revision 1.47
diff -c -p -d -u -r1.47 rtl.texi
--- doc/rtl.texi 1 Feb 2003 19:00:01 -0000 1.47
+++ doc/rtl.texi 5 Feb 2003 22:20:39 -0000
@@ -1850,7 +1850,8 @@ valid.
@item (clz:@var{m} @var{x})
Represents the number of leading 0-bits in @var{x}, represented as an
integer of mode @var{m}, starting at the most significant bit position.
-If @var{x} is zero, the value is undefined. Note that this is one of
+If @var{x} is zero, the value is determined by
+@code{CLZ_DEFINED_VALUE_AT_ZERO}. Note that this is one of
the few expressions that is not invariant under widening. The mode of
@var{x} will usually be an integer mode.
@@ -1858,7 +1859,8 @@ the few expressions that is not invarian
@item (ctz:@var{m} @var{x})
Represents the number of trailing 0-bits in @var{x}, represented as an
integer of mode @var{m}, starting at the least significant bit position.
-If @var{x} is zero, the value is undefined. Except for this case,
+If @var{x} is zero, the value is determined by
+@code{CTZ_DEFINED_VALUE_AT_ZERO}. Except for this case,
@code{ctz(x)} is equivalent to @code{ffs(@var{x}) - 1}. The mode of
@var{x} will usually be an integer mode.
Index: doc/tm.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/tm.texi,v
retrieving revision 1.198
diff -c -p -d -u -r1.198 tm.texi
--- doc/tm.texi 31 Jan 2003 23:34:17 -0000 1.198
+++ doc/tm.texi 5 Feb 2003 22:20:40 -0000
@@ -8800,6 +8800,25 @@ Define this macro on machine that have c
floating-point values. If there are no such operations, do not define
this macro.
+@findex CLZ_DEFINED_VALUE_AT_ZERO
+@findex CTZ_DEFINED_VALUE_AT_ZERO
+@item CLZ_DEFINED_VALUE_AT_ZERO (@var{mode}, @var{value})
+@itemx CTZ_DEFINED_VALUE_AT_ZERO (@var{mode}, @var{value})
+A C expression that evaluates to true if the architecture defines a value
+for @code{clz} or @code{ctz} with a zero operand. If so, @var{value}
+should be set to this value. If this macro is not defined, the value of
+@code{clz} or @code{ctz} is assumed to be undefined.
+
+This macro must be defined if the target's expansion for @code{ffs}
+relies on a particular value to get correct results. Otherwise it
+is not necessary, though it may be used to optimize some corner cases.
+
+Note that regardless of this macro the ``definedness'' of @code{clz}
+and @code{ctz} at zero do @emph{not} extend to the builtin functions
+visible to the user. Thus one may be free to adjust the value at will
+to match the target expansion of these operations without fear of
+breaking the API.
+
@findex Pmode
@item Pmode
An alias for the machine mode for pointers. On most machines, define