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

[Chris Lattner via llvm-dev]

> On Jul 5, 2020, at 5:12 AM, Nicolai Hähnle via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
>>> [1] https://en.wikipedia.org/wiki/Carry-less_product <https://en.wikipedia.org/wiki/Carry-less_product>
>>> [2] (page 30) https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf <https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf>
>>> [3] https://www.bearssl.org/constanttime.html <https://www.bearssl.org/constanttime.html>
>> What benefit would this intrinsic would bring to the middle-end IR,
>> over it's current naive expanded form?
> 
> Isn't a "naive" expansion of NxN carryless multiply extremely involved? I'd expect something like 2N shifts, N truncs, N selects, and N xors.
> 
> That link mentions an alternative that is more efficient, but I wouldn't exactly call it naive…


No, the typical expansion (used by the existing LLVM code generator) uses “grade school math” to decompose large multiplications into smaller ones.

Wide multiplications (e.g. those on X86) are pretty easy to pattern match from “sign/zero extend operands from 64 bits to 128 bits, then do a 128x128=128 multiply” for example.  This is all already handled by the existing selection dag infra, my understanding is that it works well in practice.

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200705/5b92964b/attachment.html>