https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128111
--- Comment #10 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Jakub Jelinek <[email protected]>: https://gcc.gnu.org/g:58f804554996fe057e5ca4fc814449640a6e816c commit r17-6012-g58f804554996fe057e5ca4fc814449640a6e816c Author: Jakub Jelinek <[email protected]> Date: Sat Nov 7 09:42:42 2026 +0100 c, c++, middle-end, i386: Introduce __builtin_clmulg builtin [PR128111] The https://wg21.link/P3642R7 paper proposes to add std::clmul and std::widening_clmul function templates. Because many targets have instructions to implement some cases of the carry-less product in hardware and there are various optimizations only the compiler can do and lots of different ways to open code it in the source, I think we need a builtin and pattern matching is of limited use. Now, clang added __builtin_elementwise_clmul builtin for this, but 1) we don't have any __builtin_elementwise_* builtins so far and no agreement on those 2) the builtin only provides type-generic scalar (and vector) T = clmul (T, T) operation, but many targets actually have instructions to perform widening clmul (e.g. x86 64x64->128, etc.), and because std::widening_clmul needs the latter, I think it is useful to have a builtin that can handle both So, the following patch introduces a __builtin_clmulg builtin instead, if we ever decide to add support of __builtin_elementwise_* builtins we can certainly add easily support for the clang one as well. Now, because it is a type-generic builtin, for the widening case there is a problem that we sometimes don't actually have wider types. For 32-bit targets without _BitInt there is no type wider than unsigned long long, for 64-bit targets without _BitInt there is no type wider than unsigned __int128, for _BitInt target there is no type wider than unsigned _BitInt(__BITINT_MAXWIDTH__). So, having a builtin which for 2 arguments of the same type returns some other type with precision twice as big would only work sometimes. Instead of this, the builtin has 2 or 3 arguments, as if template <__unsigned_integer T> T __builtin_clmulg (T, T); and template <__unsigned_integer T> T __builtin_clmulg (T, T, T *); where the former computes the low __builtin_popcountg ((T) ~(T) 0) bits of the result, while the latter returns the same plus stores the remaining higher bits of the result to what the third argument points to (similarly to e.g. __builtin_mul_overflow, except that __builtin_mul_overflow returns just bool, and accepts arbitrary set of types, while this one requires all of them to be the same). Under the hood, this is implemented using two new internal functions, IFN_CLMUL which returns just the low bits of the result, and IFN_CLMUL_WIDEN which is similar to IFN_MUL_OVERFLOW etc. in that it returns COMPLEX_TYPE result with real part being the low half and imag part being the high half. As for the implementation, various targets have hw instructions for some cases of this. x86 has pclmulqdq (64x64->128) and vcplmulqdq (vector version of that), arm/aarch64 has some vmul*/pmul* which can do all kinds of stuff depending on ISA (8x8->8, 8x8->16, 32x32->64, 64x64->128, powerpc has vpsum* (8x8->16, 16x16->32, 32x32->64, 64x64->128), including vector in some cases, riscv has clmul and clmulh (both together can do 32x32->64 resp. 64x64->128 depending on mode, only clmul can do 32x32 resp. 64x64) and vclmul* to handle vectors, sparc has xmulx and xmluxhi (64x64->128 together, 64x64 the first), s390x has vgfm, vgfma (8x8->16, 16x16->32, 32x32->64, 64x64->128). This patch implements just the x86 part, I'll defer to target maintainers to do the other arches. For software implementation fallback, there are various algorithms. One is the naive O(n^2), T clmul_naive (T x, T y) { T r = 0; for (int i = 0; i < __builtin_popcountg ((T) ~(T) 0); ++i) if ((unsigned) (y >> i) & 1) r ^= x << i; return r; } T2 below is unsigned type with twice the precision of T: T2 clmul_naive_widen (T x, T y) { T2 r = 0; for (int i = 0; i < __builtin_popcountg ((T) ~(T) 0); ++i) if ((unsigned) (y >> i) & 1) r ^= ((T2) x) << i; return r; } another is using Kronecker substitution, depending on maximum number of active bits in the operands and whether it is the non-widening or widening case one chooses S in [1, 13] such as for N (precision or max number of active bits) N <= S * ((1 << S) - 1) (for the widening case) or N <= S * (1 << S) (for the non-widening one; this is all about how many additions during the multiplication still don't cause carry over the given spacing, e.g. for S = 4 0x1111111111111111ULL * 0x11111111ULL is 0x8888888887654321ULL, so there is no carry over the 4 bits but one already over the 3 bits, 0x1111111111111111ULL * 0x11111111111111ULL 0xeeedcba987654321ULL so getting closer, and 0x1111111111111111ULL * 0x1111111111111111ULL being 0xfedcba987654321ULL, where there is still no carry over from one group to another within the least significant 64 bits, but there is one above that already; unsigned _BitInt(60) can use safely S = 4 even in the widening case, but unsigned _BitInt(64) only in the non-widening one and for widening it needs to use S = 5 (where 5 * 5 multiplications at least if implemented in hw is still better than 4 * 4 * 2), T clmul_kronecker (T x, T y, int S) { T mask = std::bit_repeat ((T) 1, S); T xa[S], ya[S], r = 0; for (int i = 0; i < S; ++i) { xa[i] = x & (mask << i); ya[i] = y & (mask << i); } for (int i = 0; i < S; ++i) { T t = 0; for (int j = 0; j < S; ++j) t ^= xa[j] * ya[(i + S - j) % S]; t &= (mask << i); r |= t; } return r; } T2 clmul_kronecker_widen (T x, T y, int S) { T maskn = std::bit_repeat ((T) 1, S); T2 mask = std::bit_repeat ((T2) 1, S); T2 xa[S], ya[S], r = 0; for (int i = 0; i < S; ++i) { xa[i] = x & (maskn << i); ya[i] = y & (maskn << i); } for (int i = 0; i < S; ++i) { T2 t = 0; for (int j = 0; j < S; ++j) t ^= xa[j] * ya[(i + S - j) % S]; t &= (mask << i); r |= t; } return r; } another one is recursive, e.g. adjusted Karatsuba multiplication, TH is a type with half the precision of T: T2 clmul_karatsuba_widen (T x, T y) { int N = __builtin_popcountg ((T) ~(T) 0); TH x0 = x, x1 = x >> (N / 2); TH y0 = y, y1 = y >> (N / 2); T l = clmul_widen (x0, y0); T m = clmul_widen (x0 ^ x1, y0 ^ y1); T h = clmul_widen (x1, y1); m ^= l ^ h; return (((T2) h) << N) | (((T2) m) << (N / 2)) | l; } and if we have a non-widening clmul, we can do: T2 clmul_bitreverse_widen (T x, T y) { int N = __builtin_popcountg ((T) ~(T) 0); T l = clmul (x, y); T h = __builtin_bitreverseg (clmul (__builtin_bitreverseg (x), __builtin_bitreverseg (y))) >> 1; return (((T2) h) << N) | l; } The following patch uses all of these algorithms depending on circumstances. For wi::clmul it uses the naive one, for expansion obviously attempts to use optabs first and then chooses among the rest. For _BitInt lowering, it uses an optimized version of the naive one, while theoretically a recursive algorithm could be best, we don't even handle normal multiplication that way in libgcc right now. And from my benchmarking on x86_64 (see the PR for details), the optimized version of the naive algorithm consistently beat the Kronecker one when there is no corresponding hw multiply (while the non-optimized naive was always slower than the Kronecker substitution). And the naive one is smallest in the emitted code. The patch doesn't add any libgcc libcalls right now, I'm not sure if we want to do that or not, the problem is that having too many different cases in libgcc would be code bloat for programs which don't use this, and choosing just one or two could be too slow in case we only need fewer bits. In any case, libgcc libcalls can be added later on, including in future GCC relelases. I admit I haven't figured out how the IFNs work with ranges, the only thing I know is that if the x and y operands have some trailing zeros, ctz (clmul_widen (x, y)) == ctz (x) + ctz (y), and clz (clmul_widen (x, y)) == clz (x) + clz (y) + 1. Not implemented for now, neither in CCP nor in the ranger. Possible future optimization might be to lower the two IFNs to their fallback if optabs are missing, and either let the SLP vectorizer vectorize it (it doesn't currently) or vectorize it manually, e.g. the Kronecker substitution algorithm could very well perform some vector permutations and perform e.g. 4 multiplications at a time, etc. The paper also talks about the case that clmul (x, x) can be implemented more efficiently. And perhaps we could eventually pattern match the clmul and reversed clmul of reversed args shifted down by 1 as widening clmul. The FE changes are mostly following what is done for __builtin_bswapg or __builtin_bitreverseg already, as similarly to those this is a type-generic builtin with the return type dependent on the argument type(s). 2026-11-07 Jakub Jelinek <[email protected]> PR middle-end/128111 * doc/extend.texi (__builtin_clmulg): Document. * builtins.h (fold_build_builtin_clmulg): Declare. * fold-const-call.cc (fold_const_call_sss): Handle CFN_CLMUL. (fold_const_call): Handle CFN_CLMUL_WIDEN. * internal-fn.h (expand_CLMUL, expand_CLMUL_WIDEN): Declare. * fold-const.cc (tree_call_nonnegative_p): Handle CFN_CLMUL. * wide-int.cc (wi::bit_repeat, wi::clmul): New functions. * wide-int.h (wi::bit_repeat, wi::clmul): Declare. * builtins.cc (fold_build_builtin_clmulg): New function. * internal-fn.def (CLMUL, CLMUL_WIDEN): New internal functions. * internal-fn.cc (commutative_binary_fn_p): Handle IFN_CLMUL and IFN_CLMUL_WIDEN. (expand_clmul, expand_CLMUL, expand_CLMUL_WIDEN): New functions. * optabs.def (clmul_optab, clmul_widen_optab): New optabs. * gimple-lower-bitint.cc (struct bitint_large_huge): Declare lower_clmul method. (bitint_large_huge::lower_clmul): New method. (bitint_large_huge::lower_call): Handle IFN_CLMUL. (bitint_large_huge::lower_stmt): Likewise. (stmt_needs_operand_addr): Likewise. (build_bitint_stmt_ssa_conflicts): Likewise. (gimple_lower_bitint): Lower IFN_CLMUL_WIDEN to 2 IFN_CLMUL calls, 3 IFN_BITREVERSE calls, one shift and one COMPLEX_EXPR. Handle IFN_CLMUL. * match.pd (.CLMUL (X, Y) for [0, 1] Y -> X * Y, .CLMUL_WIDEN (X, Y) -> { .CLMUL (X, 0), 0 } if upper bits are known to be zeros): New simplifications. * genmatch.cc (genmatch_diag_selftests): CFN_CLMUL and CFN_CLMUL_WIDEN are commutative. (commutative_op): Handle CFN_CLMUL and CFN_CLMUL_WIDEN. * config/i386/sse.md (clmuldi3, clmul_widendi3): New expanders. gcc/c-family/ * c-common.h (enum rid): Add RID_BUILTIN_CLMULG enumerator. * c-common.cc (c_common_reswords): Add __builtin_clmulg entry. gcc/c/ * c-parser.cc (c_parser_postfix_expression): Handle RID_BUILTIN_CLMULG. Use argument locations when reporting problems with a single argument. * c-decl.cc (names_builtin_p): Handle RID_BUILTIN_CLMULG. gcc/cp/ * parser.cc (cp_parser_postfix_expression): Handle RID_BUILTIN_CLMULG. * typeck.cc (build_x_clmulg): New function. * cp-tree.h (build_x_clmulg): Declare. * pt.cc (tsubst_expr): Handle IFN_CLMUL. * mangle.cc (write_expression): Likewise. * cp-objcp-common.cc (names_builtin_p): Handle RID_BUILTIN_CLMULG. * cp-gimplify.cc (cp_gimplify_expr): Handle IFN_CLMUL. * constexpr.cc (cxx_eval_internal_function): Likewise. (potential_constant_expression_1): Likewise. gcc/testsuite/ * c-c++-common/builtin-clmulg-1.c: New test. * c-c++-common/builtin-clmulg-2.c: New test. * g++.dg/ext/builtin-clmulg-1.C: New test. * gcc.target/i386/pclmul-builtin-clmulg-1.c: New test. Reviewed-by: Richard Biener <[email protected]> Reviewed-by: Jason Merrill <[email protected]> Reviewed-by: Marek Polacek <[email protected]>
