This patch is inspired by "lowerCTPOP" in LLVM.
Support popcount auto-vectorization by following LLVM approach.
https://godbolt.org/z/3K3GzvY7f
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 | 95 +++++++++++++++++++
.../riscv/rvv/autovec/widen/popcount-1.c | 23 +++++
.../riscv/rvv/autovec/widen/popcount_run-1.c | 50 ++++++++++
5 files changed, 182 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 b5152bc91fd..9d32b91bdca 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 a729db44c32..ae40fbb4b53 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 c10e51b362e..b3caa4b188d 100644
--- a/gcc/config/riscv/riscv-v.cc
+++ b/gcc/config/riscv/riscv-v.cc
@@ -3614,4 +3614,99 @@ 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);
+ unsigned word_size
+ = (bit_size + LONG_LONG_TYPE_SIZE - 1) / LONG_LONG_TYPE_SIZE;
+ rtx count = CONST0_RTX (mode);
+
+ for (unsigned n = 0; n < word_size; ++n)
+ {
+ rtx part_value = src;
+ for (unsigned i = 1, ct = 0;
+ i
+ < (bit_size > LONG_LONG_TYPE_SIZE ? LONG_LONG_TYPE_SIZE : 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);
+ if (bit_size > LONG_LONG_TYPE_SIZE)
+ {
+ src = expand_binop (mode, lshr_optab, src,
+ gen_int_mode (LONG_LONG_TYPE_SIZE, smode),
+ NULL_RTX, true, OPTAB_DIRECT);
+ bit_size -= LONG_LONG_TYPE_SIZE;
+ }
+ }
+ 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
