[llvm-dev] [RFC] carry-less multiplication instruction

James Y Knight via llvm-dev
2020-07-05T14:54:48Z

It'd be useful in your proposal to to note which of the existing llvm
target specific intrinsics this generic intrinsic can effectively
supersede. (E.g. llvm.x86.pclmulqdq for x86.)

When we are already supporting a given function via target specific
intrinsics for a number of different targets, that seems a pretty good
argument for making it available as a more generic target independent
intrinsic.

On Sun, Jul 5, 2020, 5:18 AM Shawn Landden via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

>
>
> Carry-less multiplication[1] instructions exist (at least optionally) on
> many architectures: armv8, RISC-V, x86_64, POWER, SPARC, C64x, and possibly
> more.
>
> This proposal is to add a llvm.clmul instruction. Or if that is
> contentious, llvm.experimental.bitmanip.clmul instruction. It takes two
> integer operands of the same width, and returns an integer with twice the
> width of the operands. (Is there a good reason to make these the same
> width, as all the other operations do even when it doesn’t really make
> sense for the mathematical operation–like multiplication or
> ctpop/ctlz/cttz?)
>
> If the CPU does not have a dedication clmul operation, it can be lowered
> to regular multiplication, by using holes to avoid carrys.
>
> ==Where is clmul used?=>
> While somewhat specialized, the RISC-V manual documents many uses: [2]
>
> The classic applications forclmulare Cyclic Redundancy Check (CRC) [11, 26]
>
> and Galois/CounterMode (GCM), but more applications exist, including the
> following examples.There are obvious applications in hashing and pseudo
> random number generations. For exam-ple, it has been reported that hashes
> based on carry-less multiplications can outperform Google’sCityHash [17].
>
> clmulof a number with itself inserts zeroes between each input bit. This
> can be useful for generatingMorton code [23].
>
> clmulof a number with -1 calculates the prefix XOR operation. This can be
> useful for decodinggray codes.Another application of XOR prefix sums
> calculated withclmulis branchless tracking of quotedstrings in
> high-performance parsers. [16]
>
> Carry-less multiply can also be used to implement Erasure code
> efficiently. [14]
>
> ==clmul lowering without hardware support=> A 8x8=>16 clmul can also
be lowered to a 32x32=>64 multiplication when
> there is no specialized instruction (also 15x15=>30, to a 60x60=>120,
or if
> bitreverse is available 16x16=>32 to TWO 64x64=>64
multiplications)[3].
>
> [1] https://en.wikipedia.org/wiki/Carry-less_product
> [2] (page 30)
>
<https://en.wikipedia.org/wiki/Carry-less_product%5B2%5D%20(page%2030)%20https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf%5B3%5D%20https://www.bearssl.org/constanttime.html>
>
https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf
> [3]
>
<https://en.wikipedia.org/wiki/Carry-less_product%5B2%5D%20(page%2030)%20https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf%5B3%5D%20https://www.bearssl.org/constanttime.html>
> https://www.bearssl.org/constanttime.html
>
>
>
> (First posted to discord
> --
> Shawn Landden
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200705/a56891ea/attachment.html>