2003-02-01 Richard Henderson <rth@redhat.com>

	* optabs.c (expand_unop): Use word_mode for outmode of bit scaners.
	* libgcc2.c (__ffsdi2, __clzsi2, __clzdi2, __ctzsi2, __ctzdi2,
	__popcountsi2, __popcountdi2, __paritysi2 __paritydi2): Change
	return type to Wtype.

	* libgcc-std.ver (GCC_3.4): Fix inheritance.

	* config/i386/i386.md (ffssi2): Use nonimmediate_operand for
	expander input constraint.

2003-02-01  Falk Hueffner  <falk.hueffner@student.uni-tuebingen.de>

        * optabs.h (optab_index): Add OTI_clz, OTI_ctz, OTI_popcount and
        OTI_parity.
        (clz_optab, ctz_optab, popcount_optab, parity_optab): New.
        * optabs.c (widen_clz, expand_parity): New.
        (expand_unop): Handle clz and parity.  Hardcode SImode as outmode
        for libcalls to clz, ctz, popcount, and parity.
        (init_optabs): Init clz_optab, ctz_optab, popcount_optab and
        parity_optab, and set up libfunc handlers.
        * libgcc2.c (__clzsi2, __clzdi2, __ctzsi2, __ctzdi2,
        __popcountsi2, __popcountdi2, __paritysi2 __paritydi2,
        __popcount_tab): New.
        * libgcc2.h: Declare them.
        * libgcc-std.ver (GCC_3.4): Add new functions from libgcc2.c.
        * genopinit.c (optabs): Add clz_optab, ctz_optab, popcount_optab
        and parity_optab.
        * builtin-types.def (BT_FN_INT_LONG, BT_FN_INT_LONGLONG): New.
        * builtins.def (BUILT_IN_CLZ, BUILT_IN_CTZ, BUILT_IN_POPCOUNT,
        BUILT_IN_PARITY, BUILT_IN_FFSL, BUILT_IN_CLZL, BUILT_IN_CTZL,
        BUILT_IN_POPCOUNTL, BUILT_IN_PARITYL, BUILT_IN_FFSLL,
        BUILT_IN_CLZLL, BUILT_IN_CTZLL, BUILT_IN_POPCOUNTLL,
        BUILT_IN_PARITYLL): New.
        * builtins.c (expand_builtin_unop): Rename from expand_builtin_ffs
        and add optab argument.
        (expand_builtin): Expand BUILT_IN_{FFS,CLZ,POPCOUNT,PARITY}*.
        * tree.def (CLZ_EXPR, CTZ_EXPR, POPCOUNT_EXPR, PARITY_EXPR): New.
        * expr.c (expand_expr): Handle them.
        * fold-const.c (tree_expr_nonnegative_p): Likewise.
        * rtl.def (CLZ, CTZ, POPCOUNT, PARITY): New.
        * reload1.c (eliminate_regs): Handle them.
        (elimination_effects): Likewise.
        * function.c (instantiate_virtual_regs_1): Likewise
        * genattrtab.c (check_attr_value): Likewise.
        * simplify-rtx.c (simplify_unary_operation): Likewise.
        * c-common.c (c_common_truthvalue_conversion): Handle POPCOUNT_EXPR.
        * combine.c (combine_simplify_rtx): Handle POPCOUNT and PARITY.
        (nonzero_bits): Handle CLZ, CTZ, POPCOUNT and PARITY.
        * config/alpha/alpha.md (clzdi2, ctzdi2, popcountdi2): New.
        * config/arm/arm.c (arm_init_builtins): Rename __builtin_clz to
        __builtin_arm_clz.
        * Makefile.in (LIB2FUNCS_1, LIB2FUNCS_2): Move...
        * mklibgcc.in (lib2funcs): ...here and merge.  Add new members.
        * doc/extend.texi (Other Builtins): Add new builtins.
        * doc/md.texi (Standard Names): Add new patterns.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@62252 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 133 insertions, 2 deletions

diff --git a/gcc/optabs.c b/gcc/optabs.c
index ea045f455e0..2b08f8efa57 100644
--- a/gcc/optabs.c
+++ b/gcc/optabs.c
@@ -126,6 +126,8 @@ static rtx expand_vector_binop PARAMS ((enum machine_mode, optab,
 					enum optab_methods));
 static rtx expand_vector_unop PARAMS ((enum machine_mode, optab, rtx, rtx,
 				       int));
+static rtx widen_clz PARAMS ((enum machine_mode, rtx, rtx));
+static rtx expand_parity PARAMS ((enum machine_mode, rtx, rtx));
 
 /* Add a REG_EQUAL note to the last insn in INSNS.  TARGET is being set to
    the result of operation CODE applied to OP0 (and OP1 if it is a binary
@@ -2325,6 +2327,89 @@ expand_simple_unop (mode, code, op0, target, unsignedp)
   return expand_unop (mode, unop, op0, target, unsignedp);
 }
 
+/* Try calculating
+	(clz:narrow x)
+   as
+	(clz:wide (zero_extend:wide x)) - ((width wide) - (width narrow)).  */
+static rtx
+widen_clz (mode, op0, target)
+     enum machine_mode mode;
+     rtx op0;
+     rtx target;
+{
+  enum mode_class class = GET_MODE_CLASS (mode);
+  if (class == MODE_INT || class == MODE_FLOAT || class == MODE_COMPLEX_FLOAT)
+    {
+      enum machine_mode wider_mode;
+      for (wider_mode = GET_MODE_WIDER_MODE (mode); wider_mode != VOIDmode;
+	   wider_mode = GET_MODE_WIDER_MODE (wider_mode))
+	{
+	  if (clz_optab->handlers[(int) wider_mode].insn_code
+	      != CODE_FOR_nothing)
+	    {
+	      rtx xop0, temp, last;
+
+	      last = get_last_insn ();
+
+	      if (target == 0)
+		target = gen_reg_rtx (mode);
+	      xop0 = widen_operand (op0, wider_mode, mode, true, false);
+	      temp = expand_unop (wider_mode, clz_optab, xop0, NULL_RTX, true);
+	      if (temp != 0)
+		temp = expand_binop (wider_mode, sub_optab, temp,
+				     GEN_INT (GET_MODE_BITSIZE (wider_mode)
+					      - GET_MODE_BITSIZE (mode)),
+				     target, true, OPTAB_DIRECT);
+	      if (temp == 0)
+		delete_insns_since (last);
+
+	      return temp;
+	    }
+	}
+    }
+  return 0;
+}
+
+/* Try calculating (parity x) as (and (popcount x) 1), where
+   popcount can also be done in a wider mode.  */
+static rtx
+expand_parity (mode, op0, target)
+     enum machine_mode mode;
+     rtx op0;
+     rtx target;
+{
+  enum mode_class class = GET_MODE_CLASS (mode);
+  if (class == MODE_INT || class == MODE_FLOAT || class == MODE_COMPLEX_FLOAT)
+    {
+      enum machine_mode wider_mode;
+      for (wider_mode = mode; wider_mode != VOIDmode;
+	   wider_mode = GET_MODE_WIDER_MODE (wider_mode))
+	{
+	  if (popcount_optab->handlers[(int) wider_mode].insn_code
+	      != CODE_FOR_nothing)
+	    {
+	      rtx xop0, temp, last;
+
+	      last = get_last_insn ();
+
+	      if (target == 0)
+		target = gen_reg_rtx (mode);
+	      xop0 = widen_operand (op0, wider_mode, mode, true, false);
+	      temp = expand_unop (wider_mode, popcount_optab, xop0, NULL_RTX,
+				  true);
+	      if (temp != 0)
+		temp = expand_binop (wider_mode, and_optab, temp, GEN_INT (1),
+				     target, true, OPTAB_DIRECT);
+	      if (temp == 0)
+		delete_insns_since (last);
+
+	      return temp;
+	    }
+	}
+    }
+  return 0;
+}
+
 /* Generate code to perform an operation specified by UNOPTAB
    on operand OP0, with result having machine-mode MODE.
 
@@ -2405,6 +2490,16 @@ expand_unop (mode, unoptab, op0, target, unsignedp)
 
   /* It can't be done in this mode.  Can we open-code it in a wider mode?  */
 
+  /* Widening clz needs special treatment.  */
+  if (unoptab == clz_optab)
+    {
+      temp = widen_clz (mode, op0, target);
+      if (temp)
+	return temp;
+      else
+	goto try_libcall;
+    }
+
   if (class == MODE_INT || class == MODE_FLOAT || class == MODE_COMPLEX_FLOAT)
     for (wider_mode = GET_MODE_WIDER_MODE (mode); wider_mode != VOIDmode;
 	 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
@@ -2560,22 +2655,39 @@ expand_unop (mode, unoptab, op0, target, unsignedp)
         }
     }
 
+  /* Try calculating parity (x) as popcount (x) % 2.  */
+  if (unoptab == parity_optab)
+    {
+      temp = expand_parity (mode, op0, target);
+      if (temp)
+	return temp;
+    }
+
+ try_libcall:
   /* Now try a library call in this mode.  */
   if (unoptab->handlers[(int) mode].libfunc)
     {
       rtx insns;
       rtx value;
+      enum machine_mode outmode = mode;
+
+      /* All of these functions return small values.  Thus we choose to
+	 have them return something that isn't a double-word.  */
+      if (unoptab == ffs_optab || unoptab == clz_optab || unoptab == ctz_optab
+	  || unoptab == popcount_optab || unoptab == parity_optab)
+	outmode = word_mode;
 
       start_sequence ();
 
       /* Pass 1 for NO_QUEUE so we don't lose any increments
 	 if the libcall is cse'd or moved.  */
       value = emit_library_call_value (unoptab->handlers[(int) mode].libfunc,
-				       NULL_RTX, LCT_CONST, mode, 1, op0, mode);
+				       NULL_RTX, LCT_CONST, outmode,
+				       1, op0, mode);
       insns = get_insns ();
       end_sequence ();
 
-      target = gen_reg_rtx (mode);
+      target = gen_reg_rtx (outmode);
       emit_libcall_block (insns, target, value,
 			  gen_rtx_fmt_e (unoptab->code, mode, op0));
 
@@ -5395,6 +5507,10 @@ init_optabs ()
   addcc_optab = init_optab (UNKNOWN);
   one_cmpl_optab = init_optab (NOT);
   ffs_optab = init_optab (FFS);
+  clz_optab = init_optab (CLZ);
+  ctz_optab = init_optab (CTZ);
+  popcount_optab = init_optab (POPCOUNT);
+  parity_optab = init_optab (PARITY);
   sqrt_optab = init_optab (SQRT);
   floor_optab = init_optab (UNKNOWN);
   ceil_optab = init_optab (UNKNOWN);
@@ -5472,6 +5588,10 @@ init_optabs ()
   init_floating_libfuncs (negv_optab, "neg", '2');
   init_integral_libfuncs (one_cmpl_optab, "one_cmpl", '2');
   init_integral_libfuncs (ffs_optab, "ffs", '2');
+  init_integral_libfuncs (clz_optab, "clz", '2');
+  init_integral_libfuncs (ctz_optab, "ctz", '2');
+  init_integral_libfuncs (popcount_optab, "popcount", '2');
+  init_integral_libfuncs (parity_optab, "parity", '2');
 
   /* Comparison libcalls for integers MUST come in pairs, signed/unsigned.  */
   init_integral_libfuncs (cmp_optab, "cmp", '2');
@@ -5531,6 +5651,17 @@ init_optabs ()
   /* The ffs function operates on `int'.  */
   ffs_optab->handlers[(int) mode_for_size (INT_TYPE_SIZE, MODE_INT, 0)].libfunc
     = init_one_libfunc ("ffs");
+  ffs_optab->handlers[(int) DImode].libfunc = init_one_libfunc ("__ffsdi2");
+  clz_optab->handlers[(int) SImode].libfunc = init_one_libfunc ("__clzsi2");
+  clz_optab->handlers[(int) DImode].libfunc = init_one_libfunc ("__clzdi2");
+  ctz_optab->handlers[(int) SImode].libfunc = init_one_libfunc ("__ctzsi2");
+  ctz_optab->handlers[(int) DImode].libfunc = init_one_libfunc ("__ctzdi2");
+  popcount_optab->handlers[(int) SImode].libfunc
+      = init_one_libfunc ("__popcountsi2");
+  popcount_optab->handlers[(int) DImode].libfunc
+      = init_one_libfunc ("__popcountdi2");
+  parity_optab->handlers[(int) SImode].libfunc = init_one_libfunc ("__paritysi2");
+  parity_optab->handlers[(int) DImode].libfunc = init_one_libfunc ("__paritydi2");
 
   extendsfdf2_libfunc = init_one_libfunc ("__extendsfdf2");
   extendsfxf2_libfunc = init_one_libfunc ("__extendsfxf2");