[PATCH] vect: Add a popcount fallback.

[Robin Dapp <rdapp.gcc@gmail.com>]

Hi,

This patch adds a fallback when the backend does not provide a popcount
implementation.  The algorithm is the same one libgcc uses, as well as
match.pd for recognizing a popcount idiom.  __builtin_ctz and __builtin_ffs
can also rely on popcount so I used the fallback for them as well.

Bootstrapped and regtested on x86, aarch64 and power10.  Unfortunately
I don't have access to any architecture other than riscv that vectorizes
but does not have a vectorized popcount.  I added all vect_int targets
to the selector where a cursory grep "expand.*popcount" would yield no
result. 

Regards
 Robin

gcc/ChangeLog:

	* tree-vect-patterns.cc (vect_have_popcount_fallback): New
	function.
	(vect_generate_popcount_fallback): New function to emit
	vectorized popcount fallback.
	(vect_recog_ctz_ffs_pattern): Use fallback.
	(vect_recog_popcount_clz_ctz_ffs_pattern): Ditto.

gcc/testsuite/ChangeLog:

	* gcc.dg/vect/vect-popcount-fallback.c: New test.
---
 .../gcc.dg/vect/vect-popcount-fallback.c      | 106 +++++++++++
 gcc/tree-vect-patterns.cc                     | 172 ++++++++++++++++--
 2 files changed, 267 insertions(+), 11 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/vect/vect-popcount-fallback.c

diff --git a/gcc/testsuite/gcc.dg/vect/vect-popcount-fallback.c b/gcc/testsuite/gcc.dg/vect/vect-popcount-fallback.c
new file mode 100644
index 00000000000..f6300f4ab35
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-popcount-fallback.c
@@ -0,0 +1,106 @@
+/* Check if we vectorize popcount when no expander is available.  */
+/* { dg-do run { target { amdgcn-*-* sparc*-*-* alpha*-*-* ia64-*-* mips*-*-* riscv*-*-* } } } */
+/* { dg-additional-options { -O2 -fdump-tree-vect-details -fno-vect-cost-model } }  */
+/* { dg-require-effective-target vect_int } */
+
+#include <stdlib.h>
+#include <assert.h>
+#include <stdint-gcc.h>
+
+__attribute__ ((noipa))
+void popc32 (uint32_t *restrict dst, uint32_t *restrict a, int n)
+{
+  for (int i = 0; i < n; i++)
+    dst[i] = __builtin_popcount (a[i]);
+}
+
+__attribute__ ((noipa))
+void ctz32 (uint32_t *restrict dst, uint32_t *restrict a, int n)
+{
+  for (int i = 0; i < n; i++)
+    dst[i] = __builtin_ctz (a[i]);
+}
+
+__attribute__ ((noipa))
+void ffs32 (uint32_t *restrict dst, uint32_t *restrict a, int n)
+{
+  for (int i = 0; i < n; i++)
+    dst[i] = __builtin_ffs (a[i]);
+}
+
+__attribute__ ((noipa))
+void popc64 (uint64_t *restrict dst, uint64_t *restrict a, int n)
+{
+  for (int i = 0; i < n; i++)
+    dst[i] = __builtin_popcountll (a[i]);
+}
+
+__attribute__ ((noipa))
+void ctz64 (uint64_t *restrict dst, uint64_t *restrict a, int n)
+{
+  for (int i = 0; i < n; i++)
+    dst[i] = __builtin_ctzll (a[i]);
+}
+
+__attribute__ ((noipa))
+void ffs64 (uint64_t *restrict dst, uint64_t *restrict a, int n)
+{
+  for (int i = 0; i < n; i++)
+    dst[i] = __builtin_ffsll (a[i]);
+}
+
+#define SZ 512
+
+__attribute__ ((optimize ("0")))
+int main ()
+{
+  uint32_t *a32pc = malloc (SZ * sizeof (*a32pc));
+  uint32_t *b32pc = malloc (SZ * sizeof (*b32pc));
+  uint32_t *a32ctz = malloc (SZ * sizeof (*a32ctz));
+  uint32_t *b32ctz = malloc (SZ * sizeof (*b32ctz));
+  uint32_t *a32ffs = malloc (SZ * sizeof (*a32ffs));
+  uint32_t *b32ffs = malloc (SZ * sizeof (*b32ffs));
+
+  uint64_t *a64pc = malloc (SZ * sizeof (*a64pc));
+  uint64_t *b64pc = malloc (SZ * sizeof (*b64pc));
+  uint64_t *a64ctz = malloc (SZ * sizeof (*a64ctz));
+  uint64_t *b64ctz = malloc (SZ * sizeof (*b64ctz));
+  uint64_t *a64ffs = malloc (SZ * sizeof (*a64ffs));
+  uint64_t *b64ffs = malloc (SZ * sizeof (*b64ffs));
+
+  for (int i = 0; i < SZ; i++)
+    {
+      int ia = i + 1;
+      a32pc[i] = ia * 1234567;
+      b32pc[i] = 0;
+      a32ctz[i] = ia * 1234567;
+      b32ctz[i] = 0;
+      a32ffs[i] = ia * 1234567;
+      b32ffs[i] = 0;
+      a64pc[i] = ia * 123456789ull;
+      b64pc[i] = 0;
+      a64ctz[i] = ia * 123456789ull;
+      b64ctz[i] = 0;
+      a64ffs[i] = ia * 123456789ull;
+      b64ffs[i] = 0;
+    }
+
+  popc32 (b32pc, a32pc, SZ);
+  ctz32 (b32ctz, a32ctz, SZ);
+  ffs32 (b32ffs, a32ffs, SZ);
+  popc64 (b64pc, a64pc, SZ);
+  ctz64 (b64ctz, a64ctz, SZ);
+  ffs64 (b64ffs, a64ffs, SZ);
+
+  for (int i = 0; i < SZ; i++)
+    {
+      assert (b32pc[i] == __builtin_popcount (a32pc[i]));
+      assert (b32ctz[i] == __builtin_ctz (a32ctz[i]));
+      assert (b32ffs[i] == __builtin_ffs (a32ffs[i]));
+      assert (b64pc[i] == __builtin_popcountll (a64pc[i]));
+      assert (b64ctz[i] == __builtin_ctzll (a64ctz[i]));
+      assert (b64ffs[i] == __builtin_ffsll (a64ffs[i]));
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "LOOP VECTORIZED" 6 "vect" target { amdgcn-*-* sparc*-*-* alpha*-*-* ia64-*-* mips*-*-* riscv*-*-* } } }  */
diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
index ef806e2346e..b812354b986 100644
--- a/gcc/tree-vect-patterns.cc
+++ b/gcc/tree-vect-patterns.cc
@@ -1782,6 +1782,122 @@ vect_recog_widen_abd_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
   return widen_abd_stmt;
 }
 
+/* Return TRUE if we have the necessary operations to create a vectorized
+   popcount for type VEC_TYPE.  */
+
+static bool
+vect_have_popcount_fallback (tree vec_type)
+{
+  return (optab_for_tree_code (RSHIFT_EXPR, vec_type, optab_scalar)
+	  && optab_for_tree_code (PLUS_EXPR, vec_type, optab_default)
+	  && optab_for_tree_code (MINUS_EXPR, vec_type, optab_default)
+	  && optab_for_tree_code (BIT_AND_EXPR, vec_type, optab_default)
+	  && optab_for_tree_code (MULT_EXPR, vec_type, optab_default));
+}
+
+/* This generates a Wilkes-Wheeler-Gill popcount similar to what libgcc
+   does (and match.pd recognizes).  There are only 32-bit and 64-bit
+   variants.
+   It returns the generated gimple sequence of vector instructions with
+   type VEC_TYPE which is being attached to STMT_VINFO.
+   RHS is the unpromoted input value and LHS_TYPE is the output type.
+   RET_VAR is the address of an SSA variable that holds the result
+   of the last operation.  It needs to be created before calling
+   this function and must have LHS_TYPE.
+
+   int popcount64c (uint64_t x)
+   {
+     x -= (x >> 1) & 0x5555555555555555ULL;
+     x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
+     x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
+     return (x * 0x0101010101010101ULL) >> 56;
+   }
+
+   int popcount32c (uint32_t x)
+   {
+     x -= (x >> 1) & 0x55555555;
+     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+     x = (x + (x >> 4)) & 0x0f0f0f0f;
+     return (x * 0x01010101) >> 24;
+   }
+   */
+
+static gimple*
+vect_generate_popcount_fallback (vec_info *vinfo, stmt_vec_info stmt_vinfo,
+				 vect_unpromoted_value rhs, tree lhs_type,
+				 tree vec_type, tree *ret_var)
+{
+  int bitsize = GET_MODE_BITSIZE (TYPE_MODE (lhs_type)).to_constant ();
+  bool is64 = bitsize == 64;
+
+  tree nuop1 = vect_convert_input (vinfo, stmt_vinfo,
+				   lhs_type, &rhs, vec_type);
+
+  tree one_cst = build_one_cst (lhs_type);
+  tree two_cst = build_int_cst (lhs_type, 2);
+  tree four_cst = build_int_cst (lhs_type, 4);
+  tree lcst = build_int_cst (lhs_type, bitsize - CHAR_BIT);
+
+  tree c1 = build_int_cst (lhs_type,
+			   is64 ? 0x5555555555555555ull : 0x55555555);
+  tree c2 = build_int_cst (lhs_type,
+			   is64 ? 0x3333333333333333ull : 0x33333333);
+  tree c4 = build_int_cst (lhs_type,
+			   is64 ? 0x0F0F0F0F0F0F0F0Full : 0x0F0F0F0F);
+  tree cm = build_int_cst (lhs_type,
+			   is64 ? 0x0101010101010101ull : 0x01010101);
+
+  gassign *g;
+
+  tree shift1 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (shift1, RSHIFT_EXPR, nuop1, one_cst);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree and1 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (and1, BIT_AND_EXPR, shift1, c1);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree x1 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (x1, MINUS_EXPR, nuop1, and1);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree shift2 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (shift2, RSHIFT_EXPR, x1, two_cst);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree and2 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (and2, BIT_AND_EXPR, shift2, c2);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree and22 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (and22, BIT_AND_EXPR, x1, c2);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree x2 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (x2, PLUS_EXPR, and2, and22);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree shift3 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (shift3, RSHIFT_EXPR, x2, four_cst);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree plus3 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (plus3, PLUS_EXPR, shift3, x2);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree x3 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (x3, BIT_AND_EXPR, plus3, c4);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  tree x4 = vect_recog_temp_ssa_var (lhs_type, NULL);
+  g = gimple_build_assign (x4, MULT_EXPR, x3, cm);
+  append_pattern_def_seq (vinfo, stmt_vinfo, g, vec_type);
+
+  g = gimple_build_assign (*ret_var, RSHIFT_EXPR, x4, lcst);
+
+  return g;
+}
+
 /* Function vect_recog_ctz_ffs_pattern
 
    Try to find the following pattern:
@@ -1894,8 +2010,9 @@ vect_recog_ctz_ffs_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
     }
   if ((ifnnew == IFN_LAST
        || (defined_at_zero && !defined_at_zero_new))
-      && direct_internal_fn_supported_p (IFN_POPCOUNT, vec_rhs_type,
-					 OPTIMIZE_FOR_SPEED))
+      && (direct_internal_fn_supported_p (IFN_POPCOUNT, vec_rhs_type,
+					 OPTIMIZE_FOR_SPEED)
+	  || vect_have_popcount_fallback (vec_rhs_type)))
     {
       ifnnew = IFN_POPCOUNT;
       defined_at_zero_new = true;
@@ -1996,9 +2113,22 @@ vect_recog_ctz_ffs_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
 
   /* Create B = .IFNNEW (A).  */
   new_var = vect_recog_temp_ssa_var (lhs_type, NULL);
-  pattern_stmt = gimple_build_call_internal (ifnnew, 1, rhs_oprnd);
-  gimple_call_set_lhs (pattern_stmt, new_var);
-  gimple_set_location (pattern_stmt, loc);
+  if (ifnnew == IFN_POPCOUNT
+      && !direct_internal_fn_supported_p (ifn, vec_type, OPTIMIZE_FOR_SPEED))
+    {
+      gcc_assert (vect_have_popcount_fallback (vec_type));
+      vect_unpromoted_value un_rhs;
+      vect_look_through_possible_promotion (vinfo, rhs_oprnd, &un_rhs);
+      pattern_stmt = vect_generate_popcount_fallback (vinfo, stmt_vinfo, un_rhs,
+						      lhs_type, vec_type,
+						      &new_var);
+    }
+  else
+    {
+      pattern_stmt = gimple_build_call_internal (ifnnew, 1, rhs_oprnd);
+      gimple_call_set_lhs (pattern_stmt, new_var);
+      gimple_set_location (pattern_stmt, loc);
+    }
   *type_out = vec_type;
 
   if (sub)
@@ -2042,6 +2172,7 @@ vect_recog_ctz_ffs_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
   return pattern_stmt;
 }
 
+
 /* Function vect_recog_popcount_clz_ctz_ffs_pattern
 
    Try to find the following pattern:
@@ -2226,12 +2357,17 @@ vect_recog_popcount_clz_ctz_ffs_pattern (vec_info *vinfo,
   if (!vec_type)
     return NULL;
 
+  bool popcount_fallback_p = false;
+
   bool supported
     = direct_internal_fn_supported_p (ifn, vec_type, OPTIMIZE_FOR_SPEED);
   if (!supported)
     switch (ifn)
       {
       case IFN_POPCOUNT:
+	if (vect_have_popcount_fallback (vec_type))
+	  popcount_fallback_p = true;
+	break;
       case IFN_CLZ:
 	return NULL;
       case IFN_FFS:
@@ -2247,7 +2383,8 @@ vect_recog_popcount_clz_ctz_ffs_pattern (vec_info *vinfo,
 					    OPTIMIZE_FOR_SPEED))
 	  break;
 	if (direct_internal_fn_supported_p (IFN_POPCOUNT, vec_type,
-					    OPTIMIZE_FOR_SPEED))
+					    OPTIMIZE_FOR_SPEED)
+	    || vect_have_popcount_fallback (vec_type))
 	  break;
 	return NULL;
       default:
@@ -2257,12 +2394,25 @@ vect_recog_popcount_clz_ctz_ffs_pattern (vec_info *vinfo,
   vect_pattern_detected ("vec_recog_popcount_clz_ctz_ffs_pattern",
 			 call_stmt);
 
-  /* Create B = .POPCOUNT (A).  */
   new_var = vect_recog_temp_ssa_var (lhs_type, NULL);
-  pattern_stmt = gimple_build_call_internal (ifn, 1, unprom_diff.op);
-  gimple_call_set_lhs (pattern_stmt, new_var);
-  gimple_set_location (pattern_stmt, gimple_location (last_stmt));
-  *type_out = vec_type;
+  if (!popcount_fallback_p)
+    {
+      /* Create B = .POPCOUNT (A).  */
+      pattern_stmt = gimple_build_call_internal (ifn, 1, unprom_diff.op);
+      gimple_call_set_lhs (pattern_stmt, new_var);
+      gimple_set_location (pattern_stmt, gimple_location (last_stmt));
+      *type_out = vec_type;
+    }
+  else
+    {
+      pattern_stmt = vect_generate_popcount_fallback (vinfo, stmt_vinfo,
+						      unprom_diff,
+						      lhs_type, vec_type,
+						      &new_var);
+      *type_out = vec_type;
+      /* For popcount we're done here.  */
+      return pattern_stmt;
+    }
 
   if (dump_enabled_p ())
     dump_printf_loc (MSG_NOTE, vect_location,
-- 
2.41.0