
<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">FWIW, this seems like a no-brainer to me (as llvm.experimental initially), assuming that it can be designed in such a way that it would eliminate the need for intrinsics on at least two targets (I think it should be possible to do so, with a small amount of back-end work).<div class=""><br class=""></div><div class="">– Steve<br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Jul 5, 2020, at 5:18 AM, Shawn Landden via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><div class=""><div class=""><br class=""></div><div class=""><div class=""><p class="">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 class="">This proposal is to add a <code class="">llvm.clmul</code> instruction. Or if that is contentious, <code class="">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 class="">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 class="">==Where is clmul used?==</p><p class="">While somewhat specialized, the RISC-V manual documents many uses: [2]</p><p class="">The classic applications forclmulare Cyclic Redundancy Check (CRC) [11, 26]</p><p class="">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 class="">clmulof a number with itself inserts zeroes between each input bit. This can be useful for generatingMorton code [23].</p><p class="">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 class="">Carry-less multiply can also be used to implement Erasure code efficiently. [14]</p><p class="">==clmul lowering without hardware support==<br class="">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 class="">[1] <a href="https://en.wikipedia.org/wiki/Carry-less_product" class="">https://en.wikipedia.org/wiki/Carry-less_product</a><br class=""><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" class="">[2] (page 30) </a><a href="https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf" class="">https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf</a><br class=""><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" class="">[3] </a><a href="https://www.bearssl.org/constanttime.html" class="">https://www.bearssl.org/constanttime.html</a></p><div class=""> <br class="webkit-block-placeholder"></div><p class="">(First posted to discord</p></div></div><div class="">-- </div><div class="">Shawn Landden</div><div class=""> </div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></body></html>