public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH V2] RISC-V: Support POPCOUNT auto-vectorization
@ 2023-07-31 14:13 Juzhe-Zhong
  2023-07-31 19:38 ` Robin Dapp
  0 siblings, 1 reply; 6+ messages in thread
From: Juzhe-Zhong @ 2023-07-31 14:13 UTC (permalink / raw)
  To: gcc-patches; +Cc: kito.cheng, kito.cheng, Juzhe-Zhong

This patch is inspired by "lowerCTPOP" in LLVM.
Support popcount auto-vectorization by LLVM approach.

Before this patch:

<source>:7:21: missed: couldn't vectorize loop
<source>:8:14: missed: not vectorized: relevant stmt not supported: _5 = __builtin_popcount (_4);

After this patch:

popcount_32:
	ble	a2,zero,.L5
	li	t3,1431654400
	li	a7,858992640
	li	t1,252645376
	li	a6,16711680
	li	a3,65536
	addiw	t3,t3,1365
	addiw	a7,a7,819
	addiw	t1,t1,-241
	addiw	a6,a6,255
	addiw	a3,a3,-1
.L3:
	vsetvli	a5,a2,e8,mf4,ta,ma
	vle32.v	v1,0(a1)
	vsetivli	zero,4,e32,m1,ta,ma
	vsrl.vi	v2,v1,1
	vand.vx	v2,v2,t3
	vsub.vv	v1,v1,v2
	vsrl.vi	v2,v1,2
	vand.vx	v2,v2,a7
	vand.vx	v1,v1,a7
	vadd.vv	v1,v1,v2
	vsrl.vi	v2,v1,4
	vadd.vv	v1,v1,v2
	vand.vx	v1,v1,t1
	vsrl.vi	v2,v1,8
	vand.vx	v2,v2,a6
	slli	a4,a5,2
	vand.vx	v1,v1,a6
	vadd.vv	v1,v1,v2
	vsrl.vi	v2,v1,16
	vand.vx	v1,v1,a3
	vand.vx	v2,v2,a3
	vadd.vv	v1,v1,v2
	vmv.v.v	v1,v1
	vsetvli	zero,a2,e32,m1,ta,ma
	sub	a2,a2,a5
	vse32.v	v1,0(a0)
	add	a1,a1,a4
	add	a0,a0,a4
	bne	a2,zero,.L3
.L5:
	ret

gcc/ChangeLog:

	* config/riscv/autovec.md (popcount<mode>2): New pattern.
	* config/riscv/riscv-protos.h (expand_popcount): New function.
	* config/riscv/riscv-v.cc (expand_popcount): Ditto.

gcc/testsuite/ChangeLog:

	* gcc.target/riscv/rvv/autovec/widen/popcount-1.c: New test.
	* gcc.target/riscv/rvv/autovec/widen/popcount_run-1.c: New test.

---
 gcc/config/riscv/autovec.md                   | 13 +++
 gcc/config/riscv/riscv-protos.h               |  1 +
 gcc/config/riscv/riscv-v.cc                   | 81 +++++++++++++++++++
 .../riscv/rvv/autovec/widen/popcount-1.c      | 23 ++++++
 .../riscv/rvv/autovec/widen/popcount_run-1.c  | 50 ++++++++++++
 5 files changed, 168 insertions(+)
 create mode 100644 gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount-1.c
 create mode 100644 gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount_run-1.c

diff --git a/gcc/config/riscv/autovec.md b/gcc/config/riscv/autovec.md
index 2094a77a9a7..7babc9756a1 100644
--- a/gcc/config/riscv/autovec.md
+++ b/gcc/config/riscv/autovec.md
@@ -922,6 +922,19 @@
   DONE;
 })
 
+;; -------------------------------------------------------------------------------
+;; - [INT] POPCOUNT.
+;; -------------------------------------------------------------------------------
+
+(define_expand "popcount<mode>2"
+  [(match_operand:VI 0 "register_operand")
+   (match_operand:VI 1 "register_operand")]
+  "TARGET_VECTOR"
+{
+  riscv_vector::expand_popcount (operands);
+  DONE;
+})
+
 ;; -------------------------------------------------------------------------------
 ;; ---- [FP] Unary operations
 ;; -------------------------------------------------------------------------------
diff --git a/gcc/config/riscv/riscv-protos.h b/gcc/config/riscv/riscv-protos.h
index 9e2c3d3e2cc..446ba7b559e 100644
--- a/gcc/config/riscv/riscv-protos.h
+++ b/gcc/config/riscv/riscv-protos.h
@@ -321,6 +321,7 @@ void expand_select_vl (rtx *);
 void expand_load_store (rtx *, bool);
 void expand_gather_scatter (rtx *, bool);
 void expand_cond_len_ternop (unsigned, rtx *);
+void expand_popcount (rtx *);
 
 /* Rounding mode bitfield for fixed point VXRM.  */
 enum fixed_point_rounding_mode
diff --git a/gcc/config/riscv/riscv-v.cc b/gcc/config/riscv/riscv-v.cc
index aa8a6763716..ac7dae952be 100644
--- a/gcc/config/riscv/riscv-v.cc
+++ b/gcc/config/riscv/riscv-v.cc
@@ -3610,4 +3610,85 @@ expand_reduction (rtx_code code, rtx *ops, rtx init, reduction_type type)
   emit_insn (gen_pred_extract_first (m1_mode, ops[0], m1_tmp2));
 }
 
+/* Expand Vector POPCOUNT by parallel popcnt:
+
+   int parallel_popcnt(uint32_t n) {
+   #define POW2(c)      (1U << (c))
+   #define MASK(c)      (static_cast<uint32_t>(-1) / (POW2(POW2(c)) + 1U))
+   #define COUNT(x, c)  ((x) & MASK(c)) + (((x)>>(POW2(c))) & MASK(c))
+	n = COUNT(n, 0);
+	n = COUNT(n, 1);
+	n = COUNT(n, 2);
+	n = COUNT(n, 3);
+	n = COUNT(n, 4);
+   //	n = COUNT(n, 5);  // uncomment this line for 64-bit integers
+	return n;
+   #undef COUNT
+   #undef MASK
+   #undef POW2
+   }
+*/
+void
+expand_popcount (rtx *ops)
+{
+  rtx dst = ops[0];
+  rtx src = ops[1];
+  machine_mode mode = GET_MODE (dst);
+  scalar_mode smode = GET_MODE_INNER (mode);
+  static const uint64_t mask_values[6]
+    = {0x5555555555555555ULL, 0x3333333333333333ULL, 0x0F0F0F0F0F0F0F0FULL,
+       0x00FF00FF00FF00FFULL, 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL};
+
+  unsigned bit_size = GET_MODE_BITSIZE (smode);
+  rtx count = CONST0_RTX (mode);
+
+  rtx part_value = src;
+  /* Currently we don't have TI vector modes so bit_size is always <= 64.  */
+  for (unsigned i = 1, ct = 0; i < bit_size; i <<= 1, ++ct)
+    {
+      rtx mask_cst = gen_int_mode (mask_values[ct], smode);
+
+      rtx vshift
+	= expand_binop (mode, lshr_optab, part_value, gen_int_mode (i, smode),
+			NULL_RTX, true, OPTAB_DIRECT);
+
+      if (i == 4)
+	{
+	  /* Optimize ((X & MASK) + ((X >> 4) & MASK))
+
+	     -> (X + (X >> 4)) & MASK  */
+	  rtx rhs = expand_binop (mode, add_optab, part_value, vshift, NULL_RTX,
+				  false, OPTAB_DIRECT);
+	  part_value = gen_reg_rtx (mode);
+	  rtx part_ops[] = {part_value, rhs, mask_cst};
+	  emit_vlmax_insn (code_for_pred_scalar (AND, mode), RVV_BINOP,
+			   part_ops);
+	}
+      else
+	{
+	  rtx rhs = gen_reg_rtx (mode);
+	  rtx rhs_ops[] = {rhs, vshift, mask_cst};
+	  emit_vlmax_insn (code_for_pred_scalar (AND, mode), RVV_BINOP,
+			   rhs_ops);
+	  if (i == 1)
+	    part_value = expand_binop (mode, sub_optab, part_value, rhs,
+				       NULL_RTX, false, OPTAB_DIRECT);
+	  else
+	    {
+	      rtx lhs = gen_reg_rtx (mode);
+	      rtx lhs_ops[] = {lhs, part_value, mask_cst};
+	      emit_vlmax_insn (code_for_pred_scalar (AND, mode), RVV_BINOP,
+			       lhs_ops);
+
+	      part_value = expand_binop (mode, add_optab, lhs, rhs, NULL_RTX,
+					 false, OPTAB_DIRECT);
+	    }
+	}
+    }
+
+  count = expand_binop (mode, add_optab, part_value, count, NULL_RTX, false,
+			OPTAB_DIRECT);
+  emit_move_insn (dst, count);
+}
+
 } // namespace riscv_vector
diff --git a/gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount-1.c b/gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount-1.c
new file mode 100644
index 00000000000..bcb4a6e8571
--- /dev/null
+++ b/gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount-1.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-march=rv32gcv_zvfh -mabi=ilp32d --param=riscv-autovec-preference=scalable -fno-vect-cost-model -fdump-tree-vect-details" } */
+
+#include <stdint-gcc.h>
+
+void __attribute__ ((noinline, noclone))
+popcount_32 (unsigned int *restrict dst, uint32_t *restrict src, int size)
+{
+  for (int i = 0; i < size; ++i)
+    dst[i] = __builtin_popcount (src[i]);
+}
+
+void __attribute__ ((noinline, noclone))
+popcount_64 (unsigned int *restrict dst, uint64_t *restrict src, int size)
+{
+  for (int i = 0; i < size; ++i)
+    dst[i] = __builtin_popcountll (src[i]);
+}
+
+/* FIXME: We don't allow vectorize "__builtin_popcountll" yet since it needs "vec_pack_trunc" support
+          and such pattern may cause inferior codegen.
+	  We will enable "vec_pack_trunc" when we support reasonable vector cost model.  */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops in function" 1 "vect" } } */
diff --git a/gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount_run-1.c b/gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount_run-1.c
new file mode 100644
index 00000000000..f6be709639a
--- /dev/null
+++ b/gcc/testsuite/gcc.target/riscv/rvv/autovec/widen/popcount_run-1.c
@@ -0,0 +1,50 @@
+/* { dg-do run { target { riscv_vector } } } */
+/* { dg-additional-options "--param=riscv-autovec-preference=scalable" } */
+
+#include "popcount-1.c"
+
+extern void abort (void) __attribute__ ((noreturn));
+
+unsigned int data[] = {
+  0x11111100, 6,
+  0xe0e0f0f0, 14,
+  0x9900aab3, 13,
+  0x00040003, 3,
+  0x000e000c, 5,
+  0x22227777, 16,
+  0x12341234, 10,
+  0x0, 0
+};
+
+int __attribute__ ((optimize (1)))
+main (void)
+{
+  unsigned int count = sizeof (data) / sizeof (data[0]) / 2;
+
+  uint32_t in32[count];
+  unsigned int out32[count];
+  for (unsigned int i = 0; i < count; ++i)
+    {
+      in32[i] = data[i * 2];
+      asm volatile ("" ::: "memory");
+    }
+  popcount_32 (out32, in32, count);
+  for (unsigned int i = 0; i < count; ++i)
+    if (out32[i] != data[i * 2 + 1])
+      abort ();
+
+  count /= 2;
+  uint64_t in64[count];
+  unsigned int out64[count];
+  for (unsigned int i = 0; i < count; ++i)
+    {
+      in64[i] = ((uint64_t) data[i * 4] << 32) | data[i * 4 + 2];
+      asm volatile ("" ::: "memory");
+    }
+  popcount_64 (out64, in64, count);
+  for (unsigned int i = 0; i < count; ++i)
+    if (out64[i] != data[i * 4 + 1] + data[i * 4 + 3])
+      abort ();
+
+  return 0;
+}
-- 
2.36.3


^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2023-08-04 20:56 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-31 14:13 [PATCH V2] RISC-V: Support POPCOUNT auto-vectorization Juzhe-Zhong
2023-07-31 19:38 ` Robin Dapp
2023-07-31 20:27   ` Robin Dapp
2023-07-31 22:03   ` 钟居哲
2023-08-01  6:47     ` Robin Dapp
2023-08-04 20:56       ` Jeff Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).