<div dir="auto"><div>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.)</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Sun, Jul 5, 2020, 5:18 AM Shawn Landden via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" rel="noreferrer noreferrer" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div> </div><div><div><p>Carry-less multiplication[1] instructions exist (at least optionally) on many architectures: armv8, RISC-V, x86_64, POWER, SPARC, C64x, and possibly more.</p><p>This proposal is to add a <code>llvm.clmul</code> instruction. Or if that is contentious, <code>llvm.experimental.bitmanip.clmul</code> 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?)</p><p>If the CPU does not have a dedication clmul operation, it can be lowered to regular multiplication, by using holes to avoid carrys.</p><p>==Where is clmul used?==</p><p>While somewhat specialized, the RISC-V manual documents many uses: [2]</p><p>The classic applications forclmulare Cyclic Redundancy Check (CRC) [11, 26]</p><p>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].</p><p>clmulof a number with itself inserts zeroes between each input bit. This can be useful for generatingMorton code [23].</p><p>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]</p><p>Carry-less multiply can also be used to implement Erasure code efficiently. [14]</p><p>==clmul lowering without hardware support==<br>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].</p><p>[1] <a href="https://en.wikipedia.org/wiki/Carry-less_product" rel="noreferrer noreferrer noreferrer" target="_blank">https://en.wikipedia.org/wiki/Carry-less_product</a><br><a href="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" rel="noreferrer noreferrer noreferrer" target="_blank">[2] (page 30) </a><a href="https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf" rel="noreferrer noreferrer noreferrer" target="_blank">https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf</a><br><a href="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" rel="noreferrer noreferrer noreferrer" target="_blank">[3] </a><a href="https://www.bearssl.org/constanttime.html" rel="noreferrer noreferrer noreferrer" target="_blank">https://www.bearssl.org/constanttime.html</a></p><p> </p><p>(First posted to discord</p></div></div><div>-- </div><div>Shawn Landden</div><div> </div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" rel="noreferrer noreferrer noreferrer" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</div></div>